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.