99 questions/80 to 89
From HaskellWiki
RossPaterson (Talk  contribs) m (new URL) 

Line 29:  Line 29:  
== Problem 81 == 
== Problem 81 == 

−  <Problem description> 
+  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. 

<pre> 
<pre> 

Example: 
Example: 

Line 36:  Line 36:  
Example in Haskell: 
Example in Haskell: 

−  <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)] 

+  [] 

</pre> 
</pre> 

Solution: 
Solution: 

<haskell> 
<haskell> 

−  <solution in haskell> 
+  import List (nub, elem) 
+  
+  data Graph a = [(a,a)] 

+  
+  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) 

</haskell> 
</haskell> 

−  <description of implementation> 
+  This solution uses a representation of a (directed) graph as a list of arcs (a,b). 
== Problem 82 == 
== Problem 82 == 
Revision as of 10:10, 7 December 2007
This is part of NinetyNine Haskell Problems, based on NinetyNine 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.
1 Graphs
2 Problem 80
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
3 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) data Graph a = [(a,a)] 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).
4 Problem 82
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
5 Problem 83
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
6 Problem 84
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
7 Problem 85
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
8 Problem 86
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
9 Problem 87
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
10 Problem 88
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
11 Problem 89
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>