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

Question

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

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 Combinator .

Я предпринял различные попыткичтобы настроить 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 of 1] Compiling Main             ( C:\maxsubseq.hs, interpreted )

C:\maxsubseq.hs:10:29:
    Occurs check: cannot construct the infinite type:
      t0 = t0 -> (([Int] -> Int) -> [Int] -> Int) -> [Int] -> Int
    In the first argument of `y', namely `y'
    In the first argument of `f', namely `(y y f)'
    In the expression: f (y y f) x

C:\maxsubseq.hs:11:29:
    Occurs check: cannot construct the infinite type:
      t0 = t0 -> (([Int] -> Int) -> [Int] -> Int) -> [Int] -> Int
    In the first argument of `y', namely `y'
    In the first argument of `f', namely `(y y f)'
    In the expression: f (y y f) x

C:\maxsubseq.hs:12:14:
    The lambda expression `\ g' gmax lmax list -> ...'
    has four arguments,
    but its type `([Int] -> Int) -> [Int] -> Int' has only two
    In the second argument of `\ y f x -> f (y y f) x', namely
      `(\ g' gmax lmax list
          -> if list == [] then
                 gmax
             else
                 g' (max gmax lmax + head list) (max 0 lmax + head list) tail list)'
    In the expression:
      (\ 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)
    In an equation for `msss'':
        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)
Failed, modules loaded: none.

Изменение с f (y y f) наf (y f) просто дает

C:\maxsubseq.hs:11:29:
    Couldn't match expected type `[Int] -> Int'
                with actual type `[Int]'
    Expected type: (([Int] -> Int) -> t1 -> t0) -> t2 -> t0
      Actual type: ([Int] -> Int) -> t1 -> t0
    In the first argument of `y', namely `f'
    In the first argument of `f', namely `(y f)'
Failed, modules loaded: none.

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

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)

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

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

Answer 1

Вы не можете определить Y комбинатор, как это в Haskell. Как вы заметили, это приводит к бесконечному типу. К счастью, он уже доступен в Data.Function как fix, где он определяется с помощью привязки let:

fix f = let x = f x in x

Answer 2

Поскольку комбинатору Y нужны бесконечные типы, вам понадобятся обходные пути , как этот .

Но я бы написал вашу msss функцию в виде одной строки:

msss = fst . foldr (\x (gmax, lmax) -> let g = max (lmax + x) in (g gmax, g 0)) (0, 0)

Answer 3

Хорошо, давайте подумаем об этом на минуту.Какой тип имеет это лямбда-выражение?

(\y f x -> f (y y f) x)

Ну f - это функция (a -> b) -> a -> b, а x - это какое-то значение b.Что это делает y?Хорошо, учитывая то, что мы только что сказали о f,

(y y f) :: (a -> b)

Кроме того, поскольку мы применяем это выражение к себе, мы знаем, что y имеет тот же тип, что и все выражение.Это та часть, где я немного озадачен.

Так что y - это волшебная функция высшего порядка.И он принимает две функции в качестве ввода.Так что это похоже на y :: f1 -> f2 -> f3.f2 имеет форму f, а f3 имеет тип результата, упомянутый выше.

y :: f1 -> ((a -> b) -> a -> b) -> (a -> b)

Вопрос в том ... что такое f1?Ну, он должен быть таким же, как тип y.Видите ли вы, как это выходит за рамки возможностей системы типов Haskell?Тип определяется в терминах самого себя.

f1 = f1 -> ((a -> b) -> a -> b) -> (a -> b)

Если вы хотите автономный «однострочник», вместо этого возьмите предложение Хаммара:

msss' = (\f -> let x = f x in x) 
        (\g' gmax lmax list -> case list of
            [] -> gmax
            (x:xs) -> g' (max gmax lmax + x) (max 0 lmax + x) xs
        ) 0 0

Хотя imho if max допустимо, тогда fix от Data.Function также должно быть допустимым.Если вы не участвуете в каком-либо конкурсе только для прелюдии.