Хаскел: Вычислить длину списка, используя (карри SND)

Question

Я было дано задание, чтобы вычислить длину списка, используя функцию foldr Haskell, так что я сделал эти два примера

flength :: [a] -> Int 
flength = foldr (\ _ n -> n+1) 0 

flength' :: [a] -> Int 
flength' l = foldr aux 0 l 
    where 
     aux _ n = n+1 

Тогда, как личный вызов, профессор попросил нас использовать функцию snd и вчера я пришел с этим:

flength'' :: [a] -> Int 
flength'' = foldr ((+1).(curry snd)) 0 

То, что я хочу, чтобы это произошло, что эта функция повернет голову списка h и аккумулятор 0 в пару (h,0) затем вернуться 0 и после этого применить его к функции (+1)

я ожидал, чтобы это было сделано рекурсивно, фактически давая мне длину списка в конце.

Вместо этого я получаю сообщение об ошибке:

[1 of 1] Compiling Main    (f1.hs, interpreted) 

f1.hs:54:24: error: 
    * No instance for (Num (Int -> Int)) 
     arising from an operator section 
     (maybe you haven't applied a function to enough arguments?) 
    * In the first argument of `(.)', namely `(+ 1)' 
     In the first argument of `foldr', namely `((+ 1) . (curry snd))' 
     In the expression: foldr ((+ 1) . (curry snd)) 0 xs 
Failed, modules loaded: none. 

Почему это происходит и как я могу получить этот код, чтобы работать?

Answer 1

Давайте отложим все наши инструменты перед нами, как хороший ремесленник делает:

foldr :: (a -> b -> b) -> b -> [a] -> b 
snd :: (a, b) -> b 

Во-первых, мы отмечаем, что snd и foldr не очень хорошо подходят. Так что давайте использовать curry, так же, как вы делали, и добавить curry snd в нашу маленькую библиотеку инструментов:

foldr  :: (a -> b -> b) -> b -> [a] -> b 
curry snd :: a -> b -> b 

Это выглядит очень перспективным. Теперь нам нужно добавить 1 к результату curry snd, иначе мы просто пишем flip const. Давайте начнем с лямбда:

\a b -> 1 + curry snd a b 
= \a b -> ((+1) . curry snd a) b 

Теперь мы можем засунуть в b и в конечном итоге с

\a -> (+1) . curry snd a 
= \a -> (.) (+1) (curry snd a) 
= \a -> ((.) (+1)) (curry snd a) 
= \a -> (((.) (+1)) . curry snd) a 

Теперь мы можем ЕТА уменьшить a с обеих сторон тоже, и в конечном итоге с

(((.) (+1)) . curry snd) = ((+1) .) . curry snd 

Таким образом, ваш третий вариант будет

flength'' = foldr (((+1) .) . curry snd) 0 

Теперь, почему вы получили сообщение об ошибке? Вы были близки с (+1) . curry snd, но типы не работают:

(+1)  :: Int -> Int 
--   v     v 
(.)  :: (b -> c) -> (a -> b  ) -> a -> c 
curry snd ::     t -> (x -> x) 
      ^     ^

Но в вашем случае, b s в подписи (.) «s не совпадают. Один из них был Int, другой был функцией.

TL; DR: Если вы хотите, чтобы написать f (g x y) точка бесплатно, написать ((f.) . g)