Seven Languages in Seven Weeks: Prolog, Day 2

factorial.prolog

fact(0, 1).
fact(N, Out) :- N > 0, N1 is N - 1, fact(N1, Prev), Out is N * Prev.

fibonacci.prolog

fib(1, 1).
fib(2, 1).
fib(N, Out) :- N > 2, N1 is N - 1, N2 is N - 2, fib(N1, Prev), fib(N2, PrevPrev), Out is Prev + PrevPrev.

idea_declarative_sort.txt

sort(list) = 
  for i in [0..list.length]
    list[i] <= list[i + 1]  

ideal_declarative_sum.txt

sum([a1, a2, a3, ..., an]) = a1 + a2 + a3 + ... + an

min.prolog

min([Head | []], Head).
min([Head | Tail], TailMin) :- min(Tail, TailMin), TailMin =< Head.
min([Head | Tail], Head) :- min(Tail, TailMin), TailMin > Head.

reverse_list.prolog

reverse_list([], []).
reverse_list([Head | Tail], Out) :- reverse_list(Tail, TailReversed), append(TailReversed, [Head], Out).

sort_list.prolog

sort_list([], []).
sort_list([Head], [Head]).
sort_list([First, Second | Tail], Sorted) :-
  divide([First, Second | Tail], Left, Right),
  sort_list(Left, LeftSorted),
  sort_list(Right, RightSorted),
  merge(LeftSorted, RightSorted, Sorted).

merge(LeftList, [], LeftList).
merge([], RightList, RightList).
merge([LeftHead | LeftTail], [RightHead | RightTail], [LeftHead | Merged]) :- 
  LeftHead =< RightHead,
  merge(LeftTail, [RightHead | RightTail], Merged).
merge([LeftHead | LeftTail], [RightHead | RightTail], [RightHead | Merged]) :- 
  LeftHead > RightHead, 
  merge([LeftHead | LeftTail], RightTail, Merged).  
  
divide([], [], []).
divide([Head], [Head], []).
divide([First, Second | Tail], [First | Left], [Second | Right]) :-
  divide(Tail, Left, Right).

sort_list_pure.prolog

sort_list(Input, Output) :-
  permutation(Input, Output),
  check_order(Output).
  
check_order([]).
check_order([Head]).
check_order([First, Second | Tail]) :-
  First =< Second,
  check_order([Second | Tail]).
  

sum_list.prolog

sum(0, []).
sum(Total, [Head | Tail]) :- sum(Sum, Tail), Total is Head + Sum.

See Seven Languages in Seven Weeks: Prolog, Day 2 for more information.