Комбинатор Y, бесконечные типы и анонимная рекурсия в Haskell

Я пытался решить задачу о максимальной сумме подпоследовательностей и нашел изящное решение

msss :: (Ord a, Num a) => [a] -> a
msss = f 0 0

f gmax _ [] = gmax
f gmax lmax (x:xs) = 
  let g = max (lmax + x)
  in  f (g gmax) (g 0) xs

Вы вызываете функцию-оболочку msss , который затем вызывает f , который, в свою очередь, выполняет всю работу. Решение хорошее и афаик работает правильно. Если бы по какой-то причине мне пришлось решать задачу максимальной суммы подпоследовательностей в производственном коде, я бы сделал это именно так.

Однако эта функция-оболочка меня действительно беспокоит. Мне нравится, как в haskell, если вы достаточно настойчивы, вы можете написать всю свою программу в одной строке, чтобы по-настоящему понять, что программа - это в значительной степени одно большое выражение. Поэтому я решил, что попробую исключить функцию-оболочку для дополнительной задачи.

Теперь я столкнулся с классической проблемой: как сделать анонимную рекурсию? Как вы делаете рекурсию, если вы не можете давать имена функциям? К счастью, отцы компьютеров решили эту проблему много лет назад, открыв комбинатор с фиксированной точкой , наиболее популярным из которых является Y-комбинатор .

Я предпринимал различные попытки настроить комбинатор Y, но они не могли пройти мимо компилятора.

msss' :: [Int] -> Int
msss' = (\y f x -> f (y y f) x) 
        (\y f x -> f (y y f) x) 
        (\g' gmax lmax list -> if list == [] 
                               then gmax 
                               else g' (max gmax lmax + head list) 
                                       (max 0    lmax + head list) 
                                       tail list)

просто дает

 Prelude>: l C: \ maxsubseq.hs
[1 из 1] Компиляция основного файла (C: \ maxsubseq.hs, интерпретировано)
C: \ maxsubseq.hs: 10: 29:
Происходит проверка: невозможно построить бесконечный тип:
t0 = t0 -> (([Int] -> Int) -> [Int] -> Int) -> [Int] -> Int
В первом аргументе y, а именно y
В первом аргументе `f ', а именно` (y y f)'
В выражении: f (y y f) x
C: \ maxsubseq.hs: 11: 29:
Происходит проверка: невозможно построить бесконечный тип:
t0 = t0 -> (([Int] -> Int) -> [Int] -> Int) -> [Int] -> Int
В первом аргументе y, а именно y
В первом аргументе `f ', а именно` (y y f)'
В выражении: f (y y f) x
C: \ maxsubseq.hs: 12: 14:
Лямбда-выражение `\ g 'gmax lmax list -> ...'
имеет четыре аргумента,
но его тип `([Int] -> Int) -> [Int] -> Int 'имеет только два
Во втором аргументе `\ y f x -> f (y y f) x ', а именно
 `(\ g 'gmax lmax список
 -> если list == [], то
gmax
еще
g '(max gmax lmax + список заголовков) (max 0 lmax + список заголовков) хвостовой список)'
В выражении:
 (\ у е х -> е (у у е) х)
 (\ у е х -> е (у у е) х)
 (\ g 'gmax lmax список
 -> если list == [], то
gmax
еще
g '(max gmax lmax + список заголовков) (max 0 lmax + список заголовков) хвостовой список)
В уравнении для "msss":
msss '
 = (\ у е х -> е (у у е) х)
 (\ у е х -> е (у у е) х)
 (\ g 'gmax lmax список
 -> если list == [], то
gmax
еще
g '(max gmax lmax + список заголовков) (max 0 lmax + список заголовков) хвостовой список)
Ошибка, модули загружены: нет.

Переход с f (y y f) на f (y f) просто дает

 C: \ maxsubseq.hs: 11: 29:
Не удалось сопоставить ожидаемый тип `[Int] -> Int '
с фактическим типом `[Int] '
Ожидаемый тип: (([Int] -> Int) -> t1 -> t0) -> t2 -> t0
Фактический тип: ([Int] -> Int) -> t1 -> t0
В первом аргументе `y ', а именно` f'
В первом аргументе `f ', а именно` (y f)'
Ошибка, модули загружены: нет.

Я пробовал использовать другой подход, просто определив комбинатор извне, но он все еще не работает и не решает мою задачу сделать это в одном выражении.

y f = f (y f)

msss' :: [Int] -> Int
msss' = y (\g' gmax lmax list -> if list == [] 
                                 then gmax 
                                 else g' (max gmax lmax + head list) 
                                         (max 0    lmax + head list) 
                                         tail list)

Вы можете заметить, что не так в том, что я делаю? Я в растерянности. Жалобы на конструирование бесконечных типов действительно раздражают меня, потому что я думал, что Haskell был посвящен таким вещам.У него бесконечные структуры данных, так почему проблема с бесконечными типами? Я подозреваю, что это как-то связано с парадоксом, который показал, что нетипизированное лямбда-исчисление непоследовательно. Хотя я не уверен. Было бы хорошо, если бы кто-нибудь мог уточнить.

Кроме того, у меня сложилось впечатление, что рекурсию всегда можно представить с помощью функций сворачивания. Может ли кто-нибудь показать мне, как я могу это сделать, просто используя складку? Тем не менее, требование, чтобы код был одним выражением, остается в силе.