Animesh Saxena
I have a simple function
fmove::Char->(Char,Char)->Char fmove s (x,y) | s == x = y | otherwise = s
If I say fmove 'a' ('a','b') it will move to 'b' If I say fmove 'a' ('d','c') it will stay at 'a'
Note that `fmove 'a' ('c','a')` won't move you to 'c' and in general `fmove x (y,z)` will move you to the node ' ' if x /= y. As for the latter I'd suggest to use Maybe to have the possibility of a miss encoded at type level: import Data.Maybe type Node = Char type Edge = (Char,Char) type Graph = [Edge] fmove:: Node -> Edge -> Maybe Node fmove s (x,y) | s == x = Just y | otherwise = Nothing
Now I am trying to use this for graph, coz one move can result in multiple result nodes.
Using mapMaybe from Data.Maybe: oneHopInGraph :: Graph -> Node -> [Node] oneHopInGraph g n = mapMaybe (fmove n) g
For example in graphs you can have move from a to b and a to c. So I was trying something like this,
:t (map fmove s) where s is the set of possible start nodes "abcd"
(map fmove s) :: [(Char, Char) -> Char]
Note that this is equivalent to `((map fmove) s)` – function application binds most in Haskell. So if you want to map from several start nodes this would be oneHopFromSeveral :: [Node] -> [Edge] -> [[Node]] oneHopFromSeveral ns g = map (oneHopInGraph g) ns
I can see that above type signature is wrong for passing the whole graph coz it accepts [(Char, Char) -> Char]. I initially started with foldl but problem is recursion on top of foldl.
My suggestion would be to take it easy in the beginning (I take it that you are a beginner): try to write the recursions yourself and really try to wrap your head around types. After writing the recursion by hand start thinking about your code and its types really hard. From time to time folds and maps will jump on you. And these Heureka moments will happen more and more frequently.
The actual objective of the problem is to figure out if a node is reachable from a start node or not. Hope the problem is clear, can anyone suggest how to convert the map function to accept the graph?
So lets see what we have here the type of the resulting function should be allPossibleHops :: Node -> Graph -> [Node] right? So what is the condition when we can stop? When there aren't any possible hops: allPossibleHops n g | oneHopInGraph g n == [] = [] in the other case the result are the next possible hops plus the result of all possible hops of these hops: | otherwise = nextHops ++ concatMap (flip allPossibleHops g) nextHops where nextHops = oneHopInGraph g n Testing: λ> allPossibleHops 'a' [('a','b'),('b','c'),('c','d'),('e','a')] "bcd" You have to make sure that there aren't any cycles for this solution to work! I hope this helps. Regards Thomas.