barbie's notes - Prolog vs Haskell


Choose the language for your problem, not the problem for your language.


Prolog vs Haskell

I have been writing lots of notes on PROLOG and some people asked me: why PROLOG? You can solve this problems in any language! And they are right! :) I also believe that it doesn’t matter which problem you have, you can solve it in any given language.

But there is more. I also believe that it is possible to find the best language for the problem you have. No one should be too attached to any language, as every single one has ups and downs!

So I decided to add here two simple examples of PROLOG code in comparison to Haskell code - both extremelly elegant IMO - and I will leave it up to you to check how it would look like in your favorite imperative language :)

The Depth-First Search is a well know algorithm, that traverses a data structure. It starts at the root and explores the branch as long as possible before backtracking.

DepthFirst

Code!

And here it goes. I am also putting them next to each other so you can compare them :)

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
dfs ::(a -> Bool) -- Goaltest (goal)
-> (a -> [a]) -- Function next (succ)
-> [a] -- StartNode
-> Maybe (a, [a]) -- Result: Just (GoalNode,Path)
-- or Nothing
dfs goal succ stack =
-- Add the Initial path, and then iterate
go [(k,[k]) | k <- stack]
where
go [] = Nothing -- Search all, nothing found
go ((k,p):r)
| goal k = Just (k,p) -- Goal found
| otherwise = go ([(k’,k’:p) | k’ <- succ k] ++ r)
Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
result(Start,Goal):-
path(Start,Goal,[],Path),
write('Path: '), % Aufruf der Tiefensuche
write(Path).

% path(StartNode, GoalNode, List of
% visited Node, ResultPath)

path(Node,Node,List,Path):-
reverse(List,Path).

path(Start,Goal,List,Path):-
edge(Start,Node),
not(member(Node,List)),
path(Node,Goal,[Node|List],Path).

The Breadth-First Search is also a search algorithm, that also traverses a data structure. The difference is that it starts at the root and explores the neighbor nodes in the same level (depth) before going to the deeper level.

BreadthFirst

Code!

And here it goes again.

Haskell
1
2
3
4
5
6
7
8
9
10
bfs goal succ start =
go [(k,[k]) | k <- start] -- create Path
where
go [] = Nothing -- nothing found
go rs =
case filter (goal . fst) rs of -- GoalNode found?
-- No, Keep checking next
[] -> go [(k’,k’:p) | (k,p) <- rs, k’ <- succ k]
-- Yes, so stop!
(r:rs) -> Just r
Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
result(Start,Goal):-
path([Start],Goal,[],Path),% Call breadth search,
%Special: StartNodes is a list
write('Path: '),
write(Path).

% path(StartNodesList, GoalNodes, List der visited
%Nodes, ResultPath)

path(Startlist,Goal,_,Path):-
Startlist=[Goal|_],
reverse(Startlist,Path).

path(Startlist,Goal,List,Path):-
Startlist=[Start|_],
findall([Nodes|Startlist],
(edge(Start,Nodes),
not(member(Nodes,Startlist))),
NodesList),
append(List,NodesList,Listnew),
Listnew=[PathN|RestPath],
path(PathN,Goal,RestPath,Path).

And if you are still not sure that some languages are better for some problems, try to check the code for this problem in Java ;) Just sayin’ !