Y комбинатор, бесконечные типы и анонимная рекурсия в Haskell
Я пытался решить проблему максимальной суммы подпоследовательности и придумал решение neato
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 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 был всем о подобных вещах. У него бесконечные структуры данных, так почему проблема с бесконечными типами? Я подозреваю, что это как-то связано с тем парадоксом, который показал, что нетипизированное лямбда-исчисление противоречиво. Я не уверен, хотя. Было бы хорошо, если бы кто-то мог уточнить.
Кроме того, у меня сложилось впечатление, что рекурсию всегда можно представить с помощью функций сгиба. Может кто-нибудь показать мне, как я могу сделать это, просто используя фолд? Требование, чтобы код был единственным выражением, все еще остается тем не менее.
3 ответа
Вы не можете определить Y комбинатор, как это в Haskell. Как вы заметили, это приводит к бесконечному типу. К счастью, он уже доступен в Data.Function как fixгде это определяется с помощью let связывание:
fix f = let x = f x in x
Поскольку комбинатору Y нужны бесконечные типы, вам понадобятся обходные пути, подобные этому.
Но я бы написал ваш 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 от Data.Function также должна быть допустимой. Если вы не участвуете в каком-либо конкурсе только для прелюдии.