99 questions/80 to 89
This is part of Ninety-Nine Haskell Problems, based on Ninety-Nine Prolog Problems.
If you want to work on one of these, put your name in the block so we know someone's working on it. Then, change n in your block to the appropriate problem number, and fill in the <Problem description>,<example in lisp>,<example in Haskell>,<solution in haskell> and <description of implementation> fields.
Graphs
Problem 80
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 81
Path from one node to another one
Write a function that, given two nodes a and b in a graph, returns all the acyclic paths from a to b.
Example: <example in lisp> Example in Haskell: paths 1 4 [(1,2),(2,3),(1,3),(3,4),(4,2),(5,6)] [[1,2,3,4],[1,3,4]] paths 2 6 [(1,2),(2,3),(1,3),(3,4),(4,2),(5,6)] []
Solution:
import List (nub, elem)
paths :: Eq a => a -> a -> [(a,a)] -> [[a]]
paths a b g = paths1 a b g []
paths1 :: Eq a => a -> a -> [(a,a)] -> [a] -> [[a]]
paths1 a b g c = paths2 a b g c [ y | (x,y) <- g, x == a ]
paths2 :: Eq a => a -> a -> [(a,a)] -> [a] -> [a] -> [[a]]
paths2 a b g c [] | a == b = [c++[b]]
| otherwise = []
paths2 a b g c (x:xs) | a == b = [c++[b]]
| elem a c = []
| otherwise = (paths1 x b g (c++[a])) ++ (paths2 a b g c xs)
This solution uses a representation of a (directed) graph as a list of arcs (a,b).
Problem 82
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 83
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 84
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 85
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 86
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 87
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 88
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 89
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>