minikanren search strategy in Haskell

GuardedKanren.hs

-- see https://gist.github.com/rntz/c2996e06301d9ae95ee0c7a9b43f5e0d for comparison
module GuardedKanren where

import Control.Monad (liftM2, guard)
import Control.Applicative

data Stream a = Nil | Cons a (Stream a) | Later (Stream a)
                deriving (Show)

instance Functor Stream where
  fmap f Nil = Nil
  fmap f (Cons x xs) = Cons (f x) (fmap f xs)
  fmap f (Later xs) = Later (fmap f xs)

instance Applicative Stream where
  pure a = Cons a Nil
  liftA2 = liftM2

instance Alternative Stream where
  empty = Nil
  Nil <|> ys = ys
  xs <|> Nil = xs
  Cons x xs <|> ys = Cons x (xs <|> ys)
  xs <|> Cons y ys = Cons y (xs <|> ys)
  Later xs <|> Later ys = Later (xs <|> ys)

instance Monad Stream where
  Nil >>= f = Nil
  Cons x xs >>= f = f x <|> (xs >>= f)
  Later xs >>= f = Later (xs >>= f)

fromList :: [a] -> Stream a
fromList [] = Nil
fromList (x:xs) = Cons x (fromList xs)

edges :: Stream (Int,Int)
edges = fromList [(1,2), (2,3), (1,3)]

trans :: Eq a => Stream (a,a) -> Stream (a,a)
trans edge = self
  where self = edge <|>
               do (x,y) <- edge
                  (y',z) <- self
                  guard $ y == y'
                  return (x,z)

reach = trans edges