Unexpected memory usage for cycle function
===

In the following program, I would only expect `cycle3` to run with constant memory (it explicitly ties the knot). However, `cycle2` also runs in constant memory for reasons I cannot fathom. I expect `cycle2` to do the exact same work as `cycle1` because


    xs' = xs ++ xs'
    xs' = xs ++ xs ++ xs' -- substitute value of xs'
    xs' = xs ++ xs ++ xs ++ xs' -- substitute value of xs' again
    xs' = xs ++ xs ++ xs ++ ... -- and so on

---

Can someone explain what I'm missing here?

---

    module Main where
    
    import System.Environment (getArgs)
    
    cycle1 :: [a] -> [a]
    cycle1 [] = error "empty list"
    cycle1 xs = xs ++ cycle1 xs
    
    cycle2 :: [a] -> [a]
    cycle2 [] = error "empty list"
    cycle2 xs = xs' where xs' = xs ++ xs'
    
    cycle3 :: [a] -> [a]
    cycle3 [] = error "empty list"
    cycle3 xs = let
      xs' = go xs' xs
      in xs'
      where
        go :: [a] -> [a] -> [a]
        go start [last] = last : start
        go start (x:xs) = x : go start xs
    
    testMem :: (Show a) => ([a] -> [a]) -> [a] -> IO ()
    testMem f xs = print (xs', xs') -- prints only first val, need second val holds onto reference
      where
        xs' = f xs
    
    main :: IO ()
    main = do
      args <- getArgs
      let mCycleFunc = case args of
            ["1"] -> Just cycle1
            ["2"] -> Just cycle2
            ["3"] -> Just cycle3
            _ -> Nothing
      case mCycleFunc of
        Just cycleFunc -> testMem cycleFunc [0..8]
        Nothing -> putStrLn "Valid args are one of {1, 2, 3}."




