Find the length of the loop

One of the popular interivew tasks… You are given a head of a linked list. Its known list contains cycle. The goal is to determine the length of the loop. Here is straghtforward solution in haskell {-data Node a instance Eq a => Eq (Node a) next :: Node a -> Node a -} data Phase = TryFindLoop | FindLength deriving (Eq) loopSize :: Eq a => Node a -> Int loopSize a = slowAndFast a a 0 TryFindLoop where slowAndFast :: (Eq node) => Node node -> Node node -> Int -> Phase -> Int slowAndFast slow fast len phase = let nextSlow = next slow nextPreFast = next fast nextFast = next nextPreFast in if (slow == nextPreFast || slow == nextFast) then if (phase == FindLength) then if (nextPreFast == nextFast) then 1 else 2*(len+1) - len - (if slow == nextFast then 0 else 1) else slowAndFast nextSlow nextSlow 0 FindLength else slowAndFast nextSlow nextFast (len + 1) phase Complexity: time o(n), memory o(1)