Warum kompiliert dieses äquivalente Programm nicht?

Question

Dieses Programm:

{-# LANGUAGE RankNTypes, ImpredicativeTypes #-} 

import qualified Data.Vector.Mutable as MV 
import qualified Data.Vector as V 
import Control.Monad.ST 
import Control.Monad.Primitive 

unsafeModify :: [(forall s . MV.MVector s Int -> ST s())] -> V.Vector Int -> V.Vector Int 
unsafeModify mods vec = runST $ do 
    mvec <- V.unsafeThaw vec 
    (mods !! 0) mvec 
    V.unsafeFreeze mvec 

Compiliert. Dieses Programm:

{-# LANGUAGE RankNTypes, ImpredicativeTypes #-} 

import qualified Data.Vector.Mutable as MV 
import qualified Data.Vector as V 
import Control.Monad.ST 
import Control.Monad.Primitive 

unsafeModify :: [(forall s . MV.MVector s Int -> ST s())] -> V.Vector Int -> V.Vector Int 
unsafeModify mods vec = runST $ do 
    mvec <- V.unsafeThaw vec 
    ($ mvec) (mods !! 0) 
    V.unsafeFreeze mvec 

lässt sich nicht kompilieren mit dem folgenden Fehler:

Muts.hs:10:15: 
    Couldn't match type ‘forall s1. UV.MVector s1 Int -> ST s1()’ 
        with ‘UV.MVector s Int -> ST s a0’ 
    Expected type: [UV.MVector s Int -> ST s a0] 
     Actual type: [forall s. UV.MVector s Int -> ST s()] 
    Relevant bindings include 
     mvec :: UV.MVector s Int (bound at Muts.hs:9:5) 
    In the first argument of ‘(!!)’, namely ‘mods’ 
    In the first argument of ‘$ mvec’, namely ‘(mods !! 0)’ 

Warum?

Answer 1

_{Hinweis: Dieser Beitrag ist in Literaten Haskell geschrieben. Sie können es als Unsafe.lhs speichern und es in Ihrem GHCi versuchen.}

---

Lassen Sie uns die Typen der verschiedenen Linien vergleichen:

mods    ::  [(forall s . MV.MVector s Int -> ST s())] 
(mods !! 0)   ::  (forall s . MV.MVector s Int -> ST s()) 
(mods !! 0) mvec ::  forall s. ST s() 


($ mvec)    ::  (MV.Vector s Int -> b) -> b 
     (mods !! 0) ::  (forall s . MV.MVector s Int -> ST s()) 
($ mvec) (mods !! 0) ::  ???????????????????????? 

Sie sind nicht gleichwertig aufgrund $ ‚s Typ:

($) :: forall a b. (a -> b) -> a -> b 

Während Sie sich etwas in

brauchen

($) :: (a ~ (forall s . MV.MVector s Int -> ST s())) => 
     (a -> b) -> a -> b 

was nicht legal ist.

Aber sehen wir uns an, was Sie eigentlich machen wollen.

> {-# LANGUAGE RankNTypes #-} 

> import qualified Data.Vector.Mutable as MV 
> import qualified Data.Vector as V 
> import Control.Monad.ST 
> import Control.Monad.Primitive 

    unsafeModify :: ??? -> V.Vector Int -> V.Vector Int 

> unsafeModify mods vec = runST $ do 
> mvec <- V.unsafeThaw vec 
> mapM_ ($ mvec) (mods !! 0) 
> V.unsafeFreeze mvec 

Dinge wurden chaotisch aufgrund unsafeModify ‚s polymorphen erste Argument mods. Ihre ursprüngliche Art

[(forall s . MV.MVector s Int -> ST s())] 

sagt uns, es ist eine Liste von Funktionen, wobei jede Funktion polymorph ist der Parameter s, so dass jede Funktion andere s nutzen könnte. Das ist jedoch zu viel. Es ist in Ordnung, wenn die s throuhgout die ganze Liste geteilt wird:

(forall s. [MV.MVector s Int -> ST s()]) 

Schließlich haben wir alle Funktionen in der gleichen ST Berechnung verwenden möchten, also die Art des Stroms Zustand Token s kann gleich sein. Wir am Ende mit

> unsafeModify :: (forall s. [MV.MVector s Int -> ST s()]) -> V.Vector Int -> V.Vector Int 

Und jetzt Ihrem Code kompiliert glücklich, unabhängig davon, ob Sie ($ mvec) (mods !! 0), (mods !! 0) mvec oder mapM_, weil s nun runST in der gesamten Liste korrekt festgelegt ist.

Answer 2

(Dies soll wohl ein Kommentar sein, aber ich mehr Platz benötigen.)

Leider imprädikative Typen funktionieren nicht sehr gut in GHC, wie @dfeuer hingewiesen. Betrachten Sie dieses Beispiel:

{-# LANGUAGE ImpredicativeTypes, PartialTypeSignatures #-} 
import qualified Data.Vector.Mutable as MV 
import Control.Monad.ST 

-- myIndex :: [forall s. MV.MVector s Int -> ST s()] 
--   -> Int 
--   -> (forall s. MV.MVector s Int -> ST s()) 
myIndex = (!!) :: [forall s. MV.MVector s Int -> ST s()] -> Int -> _ 

Es kompiliert erfolgreich, wenn auch mit einer Warnung aufgrund der Art Loch:

VectorTest.hs:9:69: Warning: 
    Found hole ‘_’ with type: forall s. MV.MVector s Int -> ST s() 
    Relevant bindings include 
     myIndex :: [forall s. MV.MVector s Int -> ST s()] 
       -> Int -> forall s. MV.MVector s Int -> ST s() 
     (bound at VectorTest.hs:9:1) 

Wir könnten versuchen, die PartialTypeSignatures Erweiterung zu entfernen und das Loch mit seiner Art forall s. MV.MVector s Int -> ST s() zu füllen. Aber dies nicht schrecklich:

VectorTest.hs:9:11: 
    Couldn't match type ‘forall s2. MV.MVector s2 Int -> ST s2()’ 
        with ‘MV.MVector s1 Int -> ST s1()’ 
    Expected type: [forall s. MV.MVector s Int -> ST s()] 
        -> Int -> MV.MVector s1 Int -> ST s1() 
     Actual type: [MV.MVector s1 Int -> ST s1()] 
        -> Int -> MV.MVector s1 Int -> ST s1() 

Die letzte forall auf der obersten Ebene gehoben wird, und jetzt GHC folgert, dass das erste Argument von (!!) muss sein, eine Liste der monomorphic Elemente [MV.MVector s1 Int -> ST s1()]trotz unserer Anmerkung! Grundsätzlich hat GHC zwei Möglichkeiten:

-- Note the hoisted forall s1 
myIndex = (!!) :: forall s1. [forall s. MV.MVector s Int -> ST s()] -> Int 
       --^first choice for instantiating the type of (!!) 
       -> MV.MVector s1 Int -> ST s1() 
       --^second choice 

GHC wählt die zweite und schlägt fehl. Nur mit einer Teilsignatur konnte ich die zweite Wahl entfernen, so dass GHC gezwungen war, das Richtige zu tun.

Wenn wir nur eine explizite Anwendung wie in GHC Core hätten, hätten wir (!!) @ (forall s. ...) schreiben können, aber leider haben wir nicht.