[Haskell-cafe] Musings on lists

[Viktor Dukhovni]

On Thu, Jul 13, 2023 at 03:39:08PM +1200, Richard O'Keefe wrote:

> 2.  xs ++ ys does copy the spine of xs.  In a strict language like
>     ML or F#, it does so right away.  In a non-strict language
>     like Haskell, it does so, but later.  If you ever explore the
>     result of xs ++ ys far enough to reach ys, you will by then
>     have copied the spine of xs.  This means that xs ++ [a] is still
>     more expensive than a : xs, it's just a matter of when the
>     payment is made.

Yes, if the list head is used more than once.  When "xs ++ ys" is used
in a fold and never seen again, no copying happens, but a thunk is
allocated.

In particular a single list append that's folded away is free, and
the below runs in constant space, regardless of the specified length.

    module Main (main) where
    import System.Environment
    import Data.Foldable

    main :: IO ()
    main = do
        fmap (read . head) getArgs >>= print . sum . xs
      where
        xs :: Int -> [Int]
        xs n = [1..n] ++ [1..n]

The real problem is with, e.g., iterated construction of a list by
appending one element at a time, depth first:

    module Main (main) where
    import System.Environment
    import Data.Foldable

    main :: IO ()
    main = do
        fmap (read . head) getArgs >>= print . sum . xs
      where
        xs :: Int -> [Int]
        xs n = go [] [1..n]
          where
            go ys [] = ys
            go ys (x : xs) = go (ys ++ [x]) xs

The space cost here is at least quadratic:

    2 x list length -> 5.1 x allocations
    3 x list length -> 12.5 x allocations
    4 x list length -> 23 x allocations
    ...

-- 
    Viktor.