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]
-}
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.