[Haskell-beginners] Function Composition/Map

[Thomas Bach]

Animesh Saxena <animeshsaxena at icloud.com> writes:

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