Путаница с каррингом и стрижкой в ​​Хаскеле - PullRequest
Новая
       43

Путаница с каррингом и стрижкой в ​​Хаскеле

9 голосов
/ 25 мая 2009

Я пытался реализовать функцию 

every :: (a -> IO Bool) -> [a] -> IO Bool

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

every f xs = liftM (all id) $ sequence $ map f xs

Моя функция не работала, так как она не была ленивой (что требовалось в вопросе), поэтому никаких голосов не было: -).

Однако я не остановился на этом. Я попытался сделать функцию бессмысленной , чтобы она была короче (и, возможно, даже круче). Поскольку аргументы f и xs являются последними в выражении, я просто отбросил их: 

every = liftM (all id) $ sequence $ map

Но это не сработало, как ожидалось, на самом деле это не сработало вообще: 

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

    stk.hs:53:42:
        Couldn't match expected type `[m a]'
               against inferred type `(a1 -> b) -> [a1] -> [b]'
        In the second argument of `($)', namely `map'
        In the second argument of `($)', namely `sequence $ map'
        In the expression: liftM (all id) $ sequence $ map
    Failed, modules loaded: none.

Почему это? У меня сложилось впечатление, что можно было просто отбросить аргументы конечной функции, что, в сущности, означает карри.

1 Ответ

25 голосов
/ 25 мая 2009

Определение $ равно 

f $ x = f x

Давайте полностью заключим в скобки вашу функцию: 

every f xs = (liftM (all id)) (sequence ((map f) xs))

и ваша версия с карри: 

every = (liftM (all id)) (sequence map)

Как вы заметили, они не идентичны. Вы можете отбросить аргументы завершающей функции только тогда, когда они применяются последним. Например, 

f x = g c x

на самом деле 

f x = (g c) x

и применение (g c) к x идет последним, так что вы можете написать 

f = g c

Один шаблон с оператором приложения $ состоит в том, что он часто становится оператором композиции. в бессчетной версии. Это потому что 

f $ g $ x

эквивалентно 

(f . g) $ x

Например, 

every f xs = liftM (all id) $ sequence $ map f xs

может стать 

every f xs = (liftM (all id) . sequence . map f) xs

в этот момент вы можете сбросить xs: 

every f = liftM (all id) . sequence . map f

Устранить аргумент f сложнее, потому что он применяется перед оператором композиции. Давайте использовать определение точки от http://www.haskell.org/haskellwiki/Pointfree:

dot = ((.) . (.))

С точками это 

(f `dot` g) x = f . g x

и это именно то, что нам нужно, чтобы каждые полные очки были свободны: 

every = (liftM (all id) . sequence) `dot` map

К сожалению, из-за ограничений в системе типов Haskell, для этого требуется явная подпись типа: 

every :: (Monad m) => (a -> m Bool) -> [a] -> m Bool
...