Day 4.5: Haskell

TLDR : The one that flew over my head

So yesterday, I finished until question 3 and decided to leave the last question for today. And now that I’ve attempted it, my brain is doing somersaults. Will post the question and answer, along with my approach and where I screwed up. This will probably be as fun as a gulag.

Question 4 : Create a function hasPath that determines if a path from one node to another exists within a directed graph.

The input for the graph is as follows : [(1,2) , (2,3) , (3,4) , (3,2)]

My solution (that absolutely didn’t work)

hasPath :: [(Int,Int)] -> Int -> Int -> Bool
hasPath [] _ _ = False
hasPath [(a,b)] _ _ = True
hasPath xs a b = elem (a,b) xs || hasPath xs y b
 where y | [] = -1
  | [x] = x
  | otherwise = ...

My reasoning was as follows. Given the directed graph and the nodes a and b and whether an edge between them existed, we should traverse the list and find the paths to which a is connected, and branch out recursively until we hit b. The problem was I didn’t know exactly how to do this in haskell.

Since we have no loops, I had to send a variable y which is a node to which a is connected. However, the main problem that arises is one of finding y, and especially feeding in y. I had no idea how to proceed without loops, if only because that’s what I’m used to.

If it was python, I would’ve put a loop feeding in every node connected to a in the recursive call. Something like below

for y in [y in (x,y) in xs]
 recursive call findPath xs y b

Anyway, the actual solution is way cooler.

Actual Solution

hasPath [] x y = x == y
hasPath xs x y
 | x == y = True
 | otherwise = let xs1 = [(n,m) | (n,m) <- xs, n/=x] in or [hasPath xs1 m y | (n,m) <- xs , n == x]

This one is a pain in the ass to understand, so I won’t try to explain it. Check out this video though, since it does.

Note : This is an O(N²) approach, so there’s that. Also, leetcode doesn’t have haskell for CP, so sucks for me.