Y combinator, бесконечные типы и анонимная рекурсия в 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
, который, в свою очередь, действительно выполняет эту работу.Решение хорошее, и afaik работает корректно.Если бы по какой-то причине мне пришлось решать задачу о максимальной сумме подпоследовательности в производственном коде, я бы сделал это именно так.
Однако эта функция-оболочка действительно доставает меня.Мне нравится, как в haskell, если вы достаточно настойчивы, вы можете написать всю свою программу в одной строке, чтобы по-настоящему донести мысль о том, что программа - это в значительной степени всего лишь одно большое выражение.Поэтому я решил, что попробую исключить функцию-оболочку для дополнительной задачи.
Именно сейчас я сталкиваюсь с классической проблемой:Как выполнить анонимную рекурсию?Как вы выполняете рекурсию, когда не можете давать имена функциям?К счастью, отцы вычислительной техники решили эту проблему давным-давно, открыв Комбинаторы с фиксированной точкой, причем наиболее популярным из них является Y - Комбинатор.
Я предпринимал различные попытки настроить Y combinator, но они не могут пройти мимо компилятора.
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)
Можете ли вы определить, что не так в том, что я делаю?Я в растерянности.Жалобы на построение бесконечных типов действительно выводят меня из себя, потому что я думал, что Haskell был полностью посвящен подобным вещам.Он имеет бесконечные структуры данных, так в чем же проблема с бесконечными типами?Я подозреваю, что это как-то связано с тем парадоксом, который показал, что нетипизированное лямбда-исчисление непоследовательно.Хотя я не уверен.Было бы хорошо, если бы кто-нибудь мог уточнить.
Кроме того, у меня сложилось впечатление, что рекурсию всегда можно представить с помощью функций fold.Кто-нибудь может показать мне, как я мог бы сделать это, просто используя сгиб?Однако требование о том, чтобы код представлял собой одно выражение, по-прежнему остается в силе.
Решение
Вы не можете определить Y combinator подобным образом в Haskell.Как вы заметили, это приводит к бесконечному типу.К счастью, он уже доступен в Data.Function
как fix
, где это определяется с помощью let
обязательный:
fix f = let x = f x in x
Другие советы
Поскольку Y combinator нуждается в бесконечных типах, вам понадобятся обходные пути как этот.
Но я бы написал тебе msss
функционируйте как однострочник, подобный этому:
msss = fst . foldr (\x (gmax, lmax) -> let g = max (lmax + x) in (g gmax, g 0)) (0, 0)
Что ж, давайте подумаем об этом минутку.Какой тип имеет это лямбда-выражение?
(\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
Хотя имхо, если max
допустимо, тогда fix
из данных.Функция также должна быть допустимой.Если только вы не участвуете в каком-нибудь конкурсе только для прелюдии.