Порядок вычисления функции в Haskell – вызов ++
Я новичок в Haskell и не понимаю, как вычисляется следующая функция:
test1 1 ls = ls
test1 p ls = test1 (p - 1) ls ++ [p]
По простой схеме ниже я предположил, что ответ должен быть [3, 2], но оценка в ghci дает [2, 3]. Почему это?
{-
test1 3 [] =
test1 2 []++[3] =
test1 1 []++[3]++[2]
-}
Спасибо, Рай-. Вот и все. Учитывая этот приоритет, я понимаю, как он оценивается.
Ответы 1
Применение функции обычно имеет приоритет над операторами, поэтому:
test1 1 ls = ls
test1 p ls = test1 (p - 1) ls ++ [p]
интерпретируется как:
test1 1 ls = ls
test1 p ls = (test1 (p - 1) ls) ++ [p]
Таким образом, это будет оценено как:
test1 3 []
-> (test1 2 []) ++ [3]
-> (test1 1 [] ++ [2]) ++ [3]
-> ([] ++ [2]) ++ [3]
-> [2, 3]
Однако алгоритм не очень эффективен: добавление справа принимает 𝓞(n) с n количеством элементов левого подсписка, в результате чего функция test1 выполняется в 𝓞(n2). Здесь мы можем работать с аккумулятором:
test1 n xs = xs ++ go n []
where go 1 xs = xs
go p xs = go (p-1) (p:xs)
Это делает алгоритм 𝓞(n). Это особенно полезно, если, например, ls уже будет очень большим списком, а также сэкономит память, поскольку мы не делаем много копий ls, а просто повторно используем список ls.
Неясно, сбивает ли вас это с толку, но обратите внимание, что приоритет
(teste1 (p - 1) ls) ++ [p]— приложение функции привязывается сильнее, чем что-либо еще.