Myhill.hs

import Data.Tuple (swap)
import Data.Bool (bool)

type N = Integer

myhill :: (N -> N) -> (N -> N) -> [(N,N)]
myhill f g = iterate False 0 [] 
  where
    iterate b x m
      | x `elem` map snd n = iterate (not b) z m
      | otherwise = p : iterate (not b) z (p : m)
      where 
        n = bool (map swap m) m b
        z = bool x (x+1) b
        p = bool (x,y) (y,x) b
        y = search (bool f g b) n x

    search f m x = let y = f x in maybe y (search f m) (lookup y m)
    
-- shorter still, but less readable
myhill2 :: (N -> N) -> (N -> N) -> [(N,N)]
myhill2 f g = iterate False 0 [] 
  where
    iterate b x m = if x `elem` map snd n then iterate (not b) z m else p : iterate (not b) z (p : m)
      where 
        z = bool x (x+1) b
        (p:n) = bool (map swap) id b ((search x, x):m)
        search x = let y = bool f g b x in maybe y search (lookup y n)