# 99 questions/80 to 89

### From HaskellWiki

RossPaterson (Talk | contribs) m (new URL) |
|||

Line 29: | Line 29: | ||

== Problem 81 == | == 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. | |

<pre> | <pre> | ||

Example: | Example: | ||

Line 36: | Line 36: | ||

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

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

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

## 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>