Tortoise-and-hare algorithm

tortoise_and_hare.hs

import Data.Array

type LinkedList = Array Int Int

-- Tests ------------------------------

makeTest :: [Int] -> LinkedList
makeTest xs = array (1, n) $ zip [1 .. n] xs
    where n = length xs

test1 :: LinkedList
test1 = makeTest ([2 .. 10] ++ [0])

test2 :: LinkedList
test2 = makeTest ([2, 3, 1])

test3 :: LinkedList
test3 = makeTest [2, 1]

-- Implementation ------------------------------

next :: LinkedList -> Int -> Int
next xs 0 = 0
next xs i = xs ! i

nextTH :: LinkedList -> (Int, Int) -> (Int, Int)
nextTH xs (t, h) = (next xs t, next xs $ next xs h)

stop :: (Int, Int) -> Bool
stop (t, h) = t == h

(|>) :: a -> (a -> b) -> b
x |> f = f x

containsCycle :: LinkedList -> Bool
containsCycle xs =  (1, 1)
                 |> iterate (nextTH xs)
                 |> tail
                 |> dropWhile (not . stop)
                 |> head
                 |> fst
                 |> (/= 0)