Многофункциональная композиция на Haskell

Question

Я пытаюсь понять состав функции в Haskell.

По данным ZVON http://zvon.org/other/haskell/Outputprelude/filter_f.html
функция фильтра должна иметь два аргумента, функцию bool и список.

пример filter (>5) [1,2,3,4,5,6,7,8] возвращает что-либо больше 5:[6,7,8]

Вопрос, как следующая строка с несколькими композициями функций переходит в логическое значение для использования фильтром?

map fst . filter snd . assocs . soeA

не должно ли это быть карта FST. фильтр (==True) и доц. soeA

Для анализа я запускаю первые две функции композиции и передаю аргумент: assocs . soeA $ 9 возвращается [(0,False),(1,False),(2,True),(3,True),(4,False),(5,True),(6,False),(7,True),(8,False),(9,False)]

soe 9 возвращается [2,3,5,7]

Каким-то образом используется значение bool в каждом элементе массива soeA, но любая помощь, объясняющая, как работает эта композиция, будет очень цениться.

Полный код:

module FastSeive where

import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed



soeST :: forall s. Int -> ST s (STUArray s Int Bool)
soeST n = do
    arr <- newArray (0, n) True
    mapM_ (\i -> writeArray arr i False) [0, 1]
    let n2 = n `div` 2

    let loop :: Int -> ST s ()
        loop i | i > n2 = return ()
        loop i = do
            b <- readArray arr i

            let reset :: Int -> ST s ()
                reset j | j > n = return ()
                reset j = writeArray arr j False >> reset (j + i)

            when b (reset (2*i))

            loop (succ i)

    loop 2
    return arr


soeA :: Int -> UArray Int Bool
soeA n = runST (soeST n >>= freeze)


soe :: Int -> [Int]
soe = map fst . filter snd . assocs . soeA


soeCount :: Int -> Int
soeCount = length . filter id . elems . soeA

`

Answer 1

Краткий ответ: здесь, snd это Boolфункция возврата filter надеется. В выражении вы написали: map fst . filter (==True) snd . assocs . soeA, snd было бы filterвторой аргумент, в то время как (==True) будет первым. Конечно, это не проверка типа, потому что filter уже применяется к двум аргументам и не может использоваться в композиции функций: это больше не функция.

---

Для более длинного ответа, мы можем применить (.)Определение, чтобы узнать, что происходит:

(f . g) x = f (g x)
-- In haskell, it is defined as being right associative

-- Meaning that if we put explicit parenthesises, we'd have:
soe = (map fst . (filter snd . (assocs . soeA)))
-- That only really matters for the compiler, though,
-- because we know function composition is associative.

soe = map fst . filter snd . assocs . soeA
-- "Un-pointfree-ing" it:
soe x = (map fst . filter snd . assocs . soeA) x
-- Applying (.)'s definition:
soe x = map fst ((filter snd . assocs . soeA) x)
-- Again:
soe x = map fst (filter snd ((assocs . soeA) x))
-- And again:
soe x = map fst (filter snd (asocs (soeA x)))

Теперь ясно, что snd является filterпервый аргумент, а второй аргумент будет оценивать, к чему assocs (soeA x) будет оценивать.

Вообще, когда кто-то пишет f . g . h, это можно прочитать справа налево как функцию, которая сначала применяется h к его аргументу, то g к результату, то f к следующему результату, и дает это окончательное значение.

---

Теперь, для еще более длинного ответа, мы можем посмотреть, как типы вашего выражения будут выведены. Это скажет нам, почему snd это Boolфункция возврата filter ожидает, даже если он имеет сигнатуру типа snd :: (a, b) -> b,

Отказ от ответственности: у меня нет опыта в разработке компиляторов; условия, которые я буду использовать, могут быть неточными.

Тип filter является (a -> Bool) -> [a] -> [a], Тип snd является (a, b) -> b,

Это на самом деле параметризованные типы. Мы можем сделать параметры типа явными:

filter :: forall a.   (a -> Bool) -> [a] -> [a]
snd    :: forall a b. (a, b) -> b

Мы также переименуем filterТип аргумента, чтобы сделать его не однозначным в том, что мы напишем дальше:

filter :: forall c. (c -> Bool) -> [c] -> [c]

filter применяется сначала к snd, Итак, мы можем попытаться объединить c -> Bool от filter с (a, b) -> b, sndтип. Мы получаем эти уравнения:

c -> Bool = (a, b) -> b

===

c = (a, b)
b = Bool

===

c = (a, Bool)
b = Bool

Мы будем предполагать, что assocs (soeA x)тип [(Int, Bool)], поскольку filterВторой аргумент имеет тип [c]Мы можем объединить дальше:

[c] = [(Int, Bool)]

===

c = (Int, Bool)

Это также дает нам:

(Int, Bool) = c = (a, Bool)

===

a = Int

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

filter :: ((Int, Bool) -> Bool) -> [(Int, Bool)] -> [(Int, Bool)]
snd    ::  (Int, Bool) -> Bool

Ну, конечно, мы могли бы использовать вывод типов GHC все время, чтобы рассказать нам об этом, либо используя GHCi, либо через плагин haskell текстового редактора.