Где ошибка в этой хвостовой рекурсивной функции Haskell?

Я должен реализовать функцию суммы в Haskell двумя способами. Одна функция с хвостовой рекурсией, а другая без хвостовой рекурсии.

Вот вариант без хвостовой рекурсии, и он отлично работает

sum1 x = if x==0 then 0 else x + sum1(x-1)

Вот моя попытка с хвостовой рекурсией, и она не работает:

sum2 x = help 0 y
help x y = if y==0 then x else help(x+y,y-1)

Может ли кто-нибудь указать на ошибку?


recursion functional-programming haskell tail-recursion
person Anil    schedule 02.05.2017    source источник
comment
Эээ, это не синтаксис для вызова функции в Haskell.   -  person Willem Van Onsem    schedule 02.05.2017
comment
Вам на самом деле все равно, но вам может быть интересно, что даже хвостовой рекурсивный вариант потребляет память для каждого шага. Поскольку haskell ленив, это создает огромные вычисления, такие как 0+500000+499999+499998..., которые выполняются только после того, как мы закончим повторяться. Исправление будет состоять в том, чтобы использовать шаблоны seq/bang или использовать какой-либо другой источник строгости, например foldl' (+) 0.   -  person Taren    schedule 03.05.2017

Ответы (1)


arrow_upward
5
arrow_downward

Ваша линия:

help x y = if y==0 then x else help(x+y,y-1)

не является правильным синтаксисом для вызова функции. Потому что здесь компилятор Haskell интерпретирует это как:

help x y = if y==0 then x else help (x+y,y-1)
--                                  ^ a tuple

Вместо этого вы должны написать:

help x y = if y==0 then x else help (x+y) (y-1)
--                                  ^ two arguments

Кроме того, вы также можете использовать охранников, например:

helper x y | y == 0 = x
           | otherwise = help (x+y) (y-1)

Наконец, есть ошибка и в первой строке sum2. Должно быть x вместо y:

sum2 x = help 0 x

Итак, в полном объеме получаем:

sum2 x = help 0 x
helper s x | x == 0 = s
           | otherwise = help (s+x) (x-1)

Я также переименовал y в helper в x и x в s (как в sum), чтобы сделать его менее запутанным (престижность @Bergi за комментарии по этому поводу).

Или используйте эта-сокращение:

sum2 = help 0

Наконец, обратите внимание, что для этого вам не нужна рекурсия. Реализация, которая будет работать быстрее, выглядит следующим образом:

sum3 x = div (x*(x+1)) 2

С:

 n
---
\       (n+1) n
/   i = -------
---        2
i=1
person Willem Van Onsem    schedule 02.05.2017
comment
Спасибо, вы мне очень помогли. Мы недавно начали с Haskell в университете, и я новичок в этом функциональном программировании. - person Anil; 02.05.2017
comment
Однако передача x в параметр y сбивает с толку. - person Bergi; 03.05.2017
comment
@Берги: Действительно. Я не смотрел на имена переменных. Я изменил код. - person Willem Van Onsem; 03.05.2017