Я пытался решить задачу максимальной суммы подпоследовательностей и придумал аккуратное решение
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)
Вы можете заметить, что не так в том, что я делаю? Я в растерянности. Жалобы на создание бесконечных типов действительно раздражают меня, потому что я думал, что Haskell был посвящен именно этому. У него бесконечные структуры данных, так почему проблема с бесконечными типами? Я подозреваю, что это как-то связано с парадоксом, который показал, что нетипизированное лямбда-исчисление непоследовательно. Хотя я не уверен. Было бы хорошо, если бы кто-нибудь мог уточнить.
Кроме того, у меня сложилось впечатление, что рекурсию всегда можно представить с помощью функций сворачивания. Может ли кто-нибудь показать мне, как я могу это сделать, просто используя складку? Тем не менее, требование, чтобы код был одним выражением, остается в силе.
0 0
в конце - person is7s   schedule 30.11.2011