Declaratieve Talen/oplossingHuffman

Dit lijkt te werken. Voel u vrij verbeteringen aan te brengen. Dit is ook absoluut niet de snelste oplossing. Zowat elke verbetering (freeze, difference list, accumulerende parameter, ...) kan hier wel ergens toegepast worden. Laat u gaan.

   decodeer(1,L,[0-L]) :- !.
   decodeer(N,L,Res) :-
       %genereer
       N2 is N - 1,
       append(L2,Tail,L),
       L2 \= [],
       Tail \= [],
       decodeer(N2,L2,Res2),
       append(Res2,[N2-Tail],Res),
       %test
       validCode(Res).
   
   %Controleert of een encodering een Huffmanencodering is
   validCode(C) :-
       findall(X,member(_-X,C),L),
       noPrefixes(L,L).
   
   %Controleert of geen enkel element van de eerste lijst een prefix is van
   %een element uit de tweede lijst
   noPrefixes([],_).
   noPrefixes([X|T],L) :-
       select(X,L,L2), %haal X zelf uit de lijst (delete werkt niet!)
       notPrefix(X,L2),
       noPrefixes(T,L).
   
   %Controleert of een gegeven lijst geen prefix is van elk element van een
   %andere lijst van lijsten.
   notPrefix(_,[]).
   notPrefix(X,[F|T]):-
       \+ append(X,_,F),
       notPrefix(X,T).
   
   beste(N,L,F,Res) :-
       findall(X,decodeer(N,L,X),Codes),
       besteCode(Codes,F,Res).
   
   besteCode([X|T],F,Res) :-
       zoekBetere(T,F,X,Res).
   
   %Dit zoekt een kortere encodering uit de lijst dan de encodering gegeven door Best.
   zoekBetere([],_,Best,Best).
   zoekBetere([X|T],F,Best,Res) :-
       berekenLengte(X,F,Len),
       berekenLengte(Best,F,BestLen),
       (Len < BestLen ->
           zoekBetere(T,F,X,Res)
       ;
           zoekBetere(T,F,Best,Res)
       ).
   
   berekenLengte([],_,0).
   berekenLengte([N-L|T],F,Len) :-
       zoekFreq(N,F,Aantal),
       length(L,LenL),
       Len2 is Aantal * LenL,
       berekenLengte(T,F,LenRest),
       Len is LenRest + Len2.
   
   zoekFreq(N,[N-Res|_],Res).
   zoekFreq(N,[_|T],Res) :-
       zoekFreq(N,T,Res).
  
  % Opm: delete werkt niet in noprefixes: 
  % delete(+List1, ?Elem, ?List2)
  % Delete all members of List1 that simultaneously unify with Elem and unify the result with List2.