Wie kann "concatMap" von mono-traversable gemeinsame Argumente "herausziehen"?

9

Ich lerne Haskell und habe ein einfaches DB-Seed-Programm für Yesod durchgeführt, als ich auf dieses Verhalten gestoßen bin, das ich schwer zu verstehen finde:

testFn :: Int -> Bool -> [Int]
testFn a b = if b then replicate 10 a else []

Jessod GHCI-Sitzung:

$ :t concatMap testFn [3]
concatMap testFn [3] :: Bool -> [Int]
$ (concatMap testFn [1,2,3]) True
[1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3]

Irgendwie war es möglich, diesen zweiten "Bool" aus jeder Zuordnung in ein einziges Curry-Argument zu "ziehen".

Die Standard-Prelude-GHCI-Basissitzung weigert sich, diesen Ausdruck überhaupt zu kompilieren:

$ :t concatMap testFn [3]
error:
     Couldn't match type 'Bool -> [Int]' with '[b]'
      Expected type: Int -> [b]
        Actual type: Int -> Bool -> [Int]
     Probable cause: 'testFn' is applied to too few arguments
      In the first argument of 'concatMap', namely 'testFn'
      In the expression: concatMap testFn [3]

Es stellt sich heraus, dass Jessod eine monotraversierbare Bibliothek verwendet, die eine eigene hat concatMap:

$ :t concatMap
concatMap
  :: (MonoFoldable mono, Monoid m) =>
     (Element mono -> m) -> mono -> m

Bei meinem derzeitigen Verständnis von Haskell konnte ich nicht herausfinden, wie die Typen hier verteilt sind. Könnte mir jemand erklären (so viel wie möglich für Anfänger), wie dieser Trick gemacht wird? Welcher Teil von testFnoben entspricht dem Element monoTyp?

dimsuz
quelle

Antworten:

6

Wir beginnen mit der Auflistung einiger uns bekannter Typen. (Wir geben vor, dass Zahlen der IntEinfachheit halber dienen - dies ist nicht wirklich relevant.)

testFn :: Int -> Bool -> [Int]
[1,2,3] :: [Int]
True :: Bool

(concatMap testFn [1,2,3]) Trueist dasselbe wie concatMap testFn [1,2,3] True, concatMapmuss also einen Typ haben, der mit all diesen Argumenten übereinstimmt:

concatMap :: (Int -> Bool -> [Int]) -> [Int] -> Bool -> ???

Wo ???ist der Ergebnistyp? Beachten Sie, dass aufgrund der Assoziativitätsregeln ->rechts assoziiert wird, sodass die obige Eingabe dieselbe ist wie:

concatMap :: (Int -> (Bool -> [Int])) -> [Int] -> (Bool -> ???)

Schreiben wir den allgemeinen Typ darüber. Ich füge ein paar Leerzeichen hinzu, um die Ähnlichkeit zu kennzeichnen.

concatMap :: (MonoFoldable mono, Monoid m) =>
             (Element mono -> m              ) -> mono  -> m
concatMap :: (Int          -> (Bool -> [Int])) -> [Int] -> (Bool -> ???)

Ah-ha! Wir haben eine Übereinstimmung, wenn wir mals Bool -> [Int]und monoals wählen [Int]. Wenn wir dies tun, erfüllen wir die Einschränkungen MonoFoldable mono, Monoid m(siehe unten), und wir haben auch Element mono ~ Int, so dass alle Typprüfungen durchgeführt werden.

Wir folgern , dass ???ist [Int]aus der Definition von m.

Über die Einschränkungen: denn MonoFoldable [Int]es gibt wenig zu sagen. [Int]ist eindeutig ein listenartiger Typ mit einem IntElementtyp, und das reicht aus, um daraus einen MonaFoldablewith Intas its zu machen Element.

Denn Monoid (Bool -> [Int])es ist etwas komplexer. Wir haben, dass jeder Funktionstyp A -> Bein Monoid ist, wenn Bes ein Monoid ist. Dies folgt, indem die Operation punktweise ausgeführt wird. In unserem speziellen Fall verlassen wir uns darauf [Int], ein Monoid zu sein, und wir bekommen:

mempty :: Bool -> [Int]
mempty = \_ -> []

(<>) :: (Bool -> [Int]) -> (Bool -> [Int]) -> (Bool -> [Int])
f <> g = \b -> f b ++ g b
Chi
quelle
1
Tolle Erklärung! Die Art und Weise, wie Sie Typen erklärt und ausgerichtet haben, ist genau das, was ich sehen wollte, danke!
Dimsuz