Reduzierung über Monads in Haskell

Question

Angenommen I einen Typ definiert haben:

data Node = forall a b. Node (SimpleWire a b) 

Die SimpleWire ist ein monadisch, wobei die Eingänge a darstellt und b repräsentiert die Ausgänge. Ich kann über diese Monade eine Funktionssteuerung durchführen. Angenommen, ich habe wireA vom Typ SimpleWire A B, und wireB vom Typ SimpleWire B C, tun wireA . wireB würde mir den Typ SimpleWire A C geben.

Jetzt möchte ich eine Liste dieser Monade umklappen (also von Typ [Node] für diesen Fall). Etwas wie:

buildGraph :: [Node] -> (SimpleWire a b) 
buildGraph (Node h):t = h . (buildGraph t) 

Wie kann ich diesen Code in Haskells Typ-System arbeiten lassen?

Answer 1

Ich werde die folgende Geschichte zu übernehmen:

Sie wahrscheinlich die Art

data Node = forall a b. Node (SimpleWire a b) 

statt nur SimpleWire a b verwendet, weil Sie eine Liste der SimpleWire ist, wo a und b sind anders wollte. Insbesondere was erhofften Sie wirklich als das Argument zu buildGraph war so etwas wie (in pseudo-Haskell)

buildGraph :: [SimpleWire a b, SimpleWire b c, ..., SimpleWire x y] -> SimpleWire a y 

Sie nicht, dass die erste Liste mit Haskell Standard homogenen [] obwohl und zu verwenden versucht universally- ausdrücken konnte quantifizierte Typen, um dich aus dieser Beize zu befreien.

Wenn das, was ich gesagt habe, wahr ist, suchen Sie wahrscheinlich nach type-threaded lists or "thrists". Insbesondere können Sie Node insgesamt abschaffen. A Thrist (->) a b ist eine Liste der Funktionen a -> a1, a1 -> a2, ..., an -> b. Allgemeiner ist eine Thrist f a b eine Liste von f s f a a1, f a1 a2, ..., f an b.

{-# LANGUAGE GADTs #-} 
import qualified Data.Thrist as DT 

-- Note that I'll be using (>>>) as a flipped form of (.), i.e. 
-- (>>>) = flip (.) 
-- (>>>) is in fact an Arrow operation which is significantly more general 
-- than function composition. Indeed your `SimpleWire` type is almost 
-- definitely an arrow. 
import Control.Arrow ((>>>)) 

-- A simple take on SimpleWire 
type SimpleWire = (->) 

-- Ugh a partial function that blows up if the thrist is empty 
unsafeBuildGraph :: DT.Thrist SimpleWire a b -> SimpleWire a b 
unsafeBuildGraph = DT.foldl1Thrist (>>>) 

-- Making it total 
buildGraph :: DT.Thrist SimpleWire a b -> Maybe (SimpleWire a b) 
buildGraph DT.Nil = Nothing 
buildGraph (wire `DT.Cons` rest) = Just $ DT.foldlThrist (>>>) wire rest 

-- For syntactic sugar 
(*::*) = DT.Cons 
infixr 6 *::* 

trivialExample :: DT.Thrist SimpleWire a a 
trivialExample = id *::* id *::* DT.Nil 

lessTrivialExample :: (Num a, Show a) => DT.Thrist SimpleWire a String 
lessTrivialExample = (+ 1) *::* (* 2) *::* show *::* DT.Nil 

-- result0 is "12" 
result0 = (unsafeBuildGraph lessTrivialExample) 5 

-- result1 is Just "12" 
result1 = fmap ($ 5) (buildGraph lessTrivialExample) 

Eine Randbemerkung:

Obwohl SimpleWire sehr gut eine Monade sein kann, das ist wahrscheinlich geht nicht direkt zu helfen. Insbesondere, während Funktionen Monaden sind, scheint es, dass Sie sich um den Begriff der Funktionszusammensetzung verallgemeinern wollen, was für die arrows ist (und die nur eine indirekte Beziehung zu Monaden haben). Es gibt Hinweise darauf, dass ich >>> verwendet habe und dass Thrist eine Arrow Instanz hat. Wie ich in den Kommentaren zu dem Code erwähne, ist SimpleWire wahrscheinlich ein Arrow.

Answer 2

Wir können [Node] mit den vorgeschlagenen Typen nicht zusammensetzen. Dies ist weil sonst würden wir

sw1 :: SimpleWire A B 
sw2 :: SimpleWire C D 
buildGraph :: [Node] -> (SimpleWire a b) 
buildGraph [ sw1, sw2 ] :: SimpleWire E F 

bekommen, die viel zu stark ist. Wir waren in der Lage, willkürliche, inkompatible Typen (falsch) zu erstellen und dann mit einem zufälligen Schreibvorgang am Ende zu enden (falsch).

Das Problem ist, dass wir alle Typinformationen im [Node] Typ verloren haben. Wir müssen einige erinnern, nämlich:

1. Die ersten und letzten Drahttypen bekannt sind (die Zwischen nicht sind)
2. in der Liste jeder benachbarten Knoten ist zusammensetzbare

Also, wir erhalten eine benutzerdefinierte GADT Listart

data NodeList a b where 
    Nil :: NodeList a a 
    Cons :: Node a b -> NodeList b c -> NodeList a c 

Und dann

buildGraph :: NodeList a b -> SimpleWire a b 
buildGraph Nil = id 
buildGraph (Cons (Node h) t) = h . buildGraph t