functionhaskellorder-of-execution

Order of evaluation of function in Haskell – call to ++


I'm new to Haskell and don't get how the following function is evaluated:

    test1 1 ls = ls
    test1 p ls = test1 (p - 1) ls ++ [p]

By the simple scheme below I assumed the answer should be [3, 2], but evaluation in ghci gives [2, 3]. Why is that?

    {-
    test1 3 [] =
        test1 2 []++[3] =
            test1 1 []++[3]++[2]
    -}

Solution

  • Function application usually takes precedence over operators, so:

    test1 1 ls = ls
    test1 p ls = test1 (p - 1) ls ++ [p]
    

    is interpreted as:

    test1 1 ls = ls
    test1 p ls = (test1 (p - 1) ls) ++ [p]
    

    This will thus get evaluated as:

    test1 3 []
      -> (test1 2 []) ++ [3]
      -> (test1 1 [] ++ [2]) ++ [3]
      -> ([] ++ [2]) ++ [3]
      -> [2, 3]
    

    The algorithm is however not very efficient: appending to the right takes 𝓞(n) with n the number of items of the left sublist, making the test1 function run in 𝓞(n2). We can work with an accumulator here:

    test1 n xs = xs ++ go n []
      where go 1 xs = xs
            go p xs = go (p-1) (p:xs)
    

    This makes the algorithm 𝓞(n). This is especially useful if for example ls would already be a very large list, and will also save memory, since we don't make a lot of copies of ls, but just reuse the ls list.