Ist es möglich, Kirchencodierungen zu verwenden, ohne die Gleichartigkeit zu brechen?

Question

Geist dieses Programm:

{-# LANGUAGE RankNTypes #-} 

import Prelude hiding (sum) 

type List h = forall t . (h -> t -> t) -> t -> t 

sum_ :: (Num a) => List a -> a 
sum_ = \ list -> list (+) 0 

toList :: [a] -> List a 
toList = \ list cons nil -> foldr cons nil list 

sum :: (Num a) => [a] -> a 
-- sum = sum_ . toList  -- does not work 
sum = \ a -> sum_ (toList a) -- works 

main = print (sum [1,2,3]) 

Beide Definitionen der Summe sind equational Argumentation gleich hoch. Doch die Erstellung der zweiten Definition von Werken, aber der erste nicht, mit diesem Fehler:

tmpdel.hs:17:14: 
    Couldn't match type ‘(a -> t0 -> t0) -> t0 -> t0’ 
        with ‘forall t. (a -> t -> t) -> t -> t’ 
    Expected type: [a] -> List a 
     Actual type: [a] -> (a -> t0 -> t0) -> t0 -> t0 
    Relevant bindings include sum :: [a] -> a (bound at tmpdel.hs:17:1) 
    In the second argument of ‘(.)’, namely ‘toList’ 
    In the expression: sum_ . toList 

Es scheint, dass RankNTypes Pausen Argumentation equational. Gibt es eine Möglichkeit, kirchenkodierte Listen in Haskell zu haben, ohne sie zu brechen?

Answer 1

Ich habe den Eindruck, dass ghc alle so links wie möglich für-all sickert:

forall a t. [a] -> (a -> t -> t) -> t -> t) 

und

forall a. [a] -> forall t . (h -> t -> t) -> t -> t 

austauschbar als Zeuge von verwendet werden:

toList' :: forall a t. [a] -> (a -> t -> t) -> t -> t 
toList' = toList 

toList :: [a] -> List a 
toList = toList' 

Das könnte erklären, warum der Typ sum nicht überprüft werden kann. Sie können diese Art von Problemen vermeiden, indem Sie Ihre polymorphe Definition in einem newtype Wrapper, um zu vermeiden, dass hoisting (dieser Absatz erscheint nicht in neueren Versionen des Dokuments daher meine Verwendung der Bedingung früher).

Answer 2

Hier ist ein etwas beängstigender Trick, den Sie versuchen könnten. Überall wo Sie eine Rang-2-Variable haben würden, verwenden Sie stattdessen einen leeren Typ; und überall wo Sie eine Instanziierung der Typvariablen auswählen würden, verwenden Sie unsafeCoerce. Die Verwendung eines leeren Typs stellt sicher, dass Sie (so viel wie möglich) nichts tun, was einen unbeobachtbaren Wert beobachten kann. Daraus folgt:

import Data.Void 
import Unsafe.Coerce 

type List a = (a -> Void -> Void) -> Void -> Void 

toList :: [a] -> List a 
toList xs = \cons nil -> foldr cons nil xs 

sum_ :: Num a => List a -> a 
sum_ xs = unsafeCoerce xs (+) 0 

main :: IO() 
main = print (sum_ . toList $ [1,2,3]) 

Vielleicht möchten Sie eine etwas sicherere Version von unsafeCoerce schreiben, wie:

instantiate :: List a -> (a -> r -> r) -> r -> r 
instantiate = unsafeCoerce 

Dann sum_ xs = instantiate xs (+) 0 funktioniert gut als Alternative Definition, und Sie nicht das Risiko des Drehens laufen Ihre List a in etwas wahrlich willkürlich.

Answer 3

Im Allgemeinen gilt die Gleichsetzung nur im "zugrunde liegenden System F", das Haskell darstellt. In diesem Fall, wie andere bemerkt haben, stolpern Sie, weil Haskell forall s nach links bewegt und automatisch die richtigen Typen an verschiedenen Punkten anwendet. Sie können es beheben, indem Sie Hinweise dazu angeben, wo die Anwendung über Wrapper erfolgen soll. Wie Sie gesehen haben, können Sie auch manipulieren, wenn die Typ-Anwendung durch eta-Erweiterung erfolgt, da die Hindley-Milner-Typisierungsregeln für let und für Lambda: forall s über die "Generalisierungs" -Regel standardmäßig unter let s (und andere, gleichwertige benannte Bindungen) allein.