Difference between revisions of "99 questions/80 to 89"
m |
|||
| Line 44: | Line 44: | ||
Solution: |
Solution: |
||
<haskell> |
<haskell> |
||
| − | import List ( |
+ | import List (elem) |
paths :: Eq a => a -> a -> [(a,a)] -> [[a]] |
paths :: Eq a => a -> a -> [(a,a)] -> [[a]] |
||
| Line 50: | Line 50: | ||
paths1 :: Eq a => a -> a -> [(a,a)] -> [a] -> [[a]] |
paths1 :: Eq a => a -> a -> [(a,a)] -> [a] -> [[a]] |
||
| − | paths1 a b g |
+ | paths1 a b g current = paths2 a b g current [ y | (x,y) <- g, x == a ] |
paths2 :: Eq a => a -> a -> [(a,a)] -> [a] -> [a] -> [[a]] |
paths2 :: Eq a => a -> a -> [(a,a)] -> [a] -> [a] -> [[a]] |
||
| − | paths2 a b g |
+ | paths2 a b g current [] | a == b = [current++[b]] |
| otherwise = [] |
| otherwise = [] |
||
| − | paths2 a b g |
+ | paths2 a b g current (x:xs) | a == b = [current++[b]] |
| − | | elem a |
+ | | elem a current = [] |
| − | | otherwise = (paths1 x b g ( |
+ | | otherwise = (paths1 x b g (current++[a])) ++ (paths2 a b g current xs) |
</haskell> |
</haskell> |
||
Revision as of 12:41, 7 December 2007
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 (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 current = paths2 a b g current [ y | (x,y) <- g, x == a ]
paths2 :: Eq a => a -> a -> [(a,a)] -> [a] -> [a] -> [[a]]
paths2 a b g current [] | a == b = [current++[b]]
| otherwise = []
paths2 a b g current (x:xs) | a == b = [current++[b]]
| elem a current = []
| otherwise = (paths1 x b g (current++[a])) ++ (paths2 a b g current 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>