Haskell: a -> a -> ... -> b [a] -> b

Question

Ich versuche, die folgende Karte als Haskell Funktion zum Ausdruck bringen:

Gegeben seien zwei Arten a, b die Familie betrachten Funktionen F(a, b) von Funktionen der Art, die aus

f :: a -> a -> ... -> a -> b 

mit n Wiederholungen a, wo n eine ganze Zahl größer als Null ist. Was ich will, ist jede Funktion f in F(a, b) auf eine Funktion zur Karte f' :: [a] -> b, so dass f x1 x2 ... xr = f' [x1, ..., xr], wo r kleiner ist als die Anzahl der Argumente ist f nimmt (das heißt ich bin für die Funktion der Suche listify :: F(a, b) -> ([a] -> b)). Wenn es mehr Elemente als f Argumente verwendet, sollten die zusätzlichen Elemente verworfen werden:

f :: a -> a -> b 
(listify f xs) == (listify f $ take 2 xs) 

Außerdem, wenn die leeren kotierten übergeben wird, wird jeder Wert akzeptabel ist.

Ich bin natürlich in der Lage, diese Karte für Funktionen mit einer festen Anzahl von Argumenten zu implementieren (zum Beispiel: listify :: (a -> a -> b) -> ([a] -> b), etc.), aber ich konnte keinen Weg finden, eine Funktion zu schreiben, die es für alle f tut in F(a, b) gleichzeitig. Obwohl Template Haskell wahrscheinlich in der Lage ist, mir die richtigen Werkzeuge zur Verfügung zu stellen, interessiert mich eine solche Lösung nicht. Ich möchte etwas pure "Art Magie" finden, um es zu tun.

Weiß jemand, ob das überhaupt möglich ist? Kann mir jemand vielleicht in die richtige Richtung zeigen? Oder ist das ein bekanntes "Problem", das Milliarden Mal gelöst wurde und ich einfach keine Lösung finden kann?

Answer 1

Wir müssen nur unser Gift hier holen. Wenn wir weniger sichere Pragmas verwenden, können wir mehr Schlussfolgerungen ziehen und umgekehrt; Es gibt eine Reihe von Kombinationen.

Erste: überlappende Instanzen verwendet, hat nicht funktioniert als Basisfall, kann aber polymorphe a Typen nicht umgehen:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances #-} 

class Listify a b where 
    listify :: a -> b 

instance {-# OVERLAPS #-} r ~ ([a] -> b) => Listify b r where 
    listify = const 

instance (Listify f r, r ~ ([a] -> b)) => Listify (a -> f) r where 
    listify f (a:as) = listify (f a) as 

-- listify (+) [0, 2] -- error 
-- listify (+) [0, 2 :: Int] -- OK 
-- listify() [] -- OK 

Zweite: verwendet überlappende Instanzen, hat Funktionen als Basisfall, polymorphe Typen verarbeiten kann:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances, FlexibleContexts #-} 

class Listify a b where 
    listify :: a -> b 

instance {-# OVERLAPS #-} r ~ ([a] -> b) => Listify (a -> b) r where 
    listify f (a:_) = f a 

instance (Listify (a -> b) r, r ~ ([a] -> b)) => Listify (a -> a -> b) r where 
    listify f (a:as) = listify (f a) as 

-- listify (+) [0, 2] -- OK 
-- listify() [] -- error, first arg must be a function 

Dritte: verwendet inkohärent Fällen hat Werte in Basisfall können polymorphe Arten behandeln:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances #-} 

class Listify a b where 
    listify :: a -> b 

instance {-# INCOHERENT #-} r ~ ([a] -> b) => Listify b r where 
    listify = const 

instance (Listify f r, r ~ ([a] -> b)) => Listify (a -> f) r where 
    listify f (a:as) = listify (f a) as 

-- listify 0 [] -- OK 
-- listify (+) [2, 4] -- OK 

Vierte: geschlossene Familien zum Beispiel Auflösung mit UndecidableInstances als Helfer verwendet, hat Werte in Basisfall können polymorphe Typen nicht umgehen:

{-# LANGUAGE UndecidableInstances, ScopedTypeVariables, DataKinds, 
    TypeFamilies, MultiParamTypeClasses, FlexibleInstances, FlexibleContexts #-} 

import Data.Proxy 

data Nat = Z | S Nat 

type family Arity f where 
    Arity (a -> b) = S (Arity b) 
    Arity b  = Z 

class Listify (n :: Nat) a b where 
    listify' :: Proxy n -> a -> b 

instance r ~ (a -> b) => Listify Z b r where 
    listify' _ = const 

instance (Listify n f r, a ~ (a' -> f), r ~ ([a'] -> b)) => Listify (S n) a r where 
    listify' _ f (a:as) = listify' (Proxy :: Proxy n) (f a) as 

listify :: forall a b. Listify (Arity a) a b => a -> b 
listify = listify' (Proxy :: Proxy (Arity a)) 

-- listify (+) [3, 4] -- error 
-- listify (+) [3, 4::Int] -- OK 
-- listify() [] -- OK 
-- listify 0 [] -- error 
-- listify (0 :: Int) [] -- OK 

Von der Spitze meines Kopfes, in etwa sind das die Varianten, die man in freier Wildbahn sehen kann, mit Ausnahme der INCOHERENT, weil das im Bibliothekscode extrem selten ist (aus guten Gründen).

Ich persönlich empfehle die Version mit den geschlossenen Typ Familien, denn UndecidableInstances und Typ Familien sind bei weitem am wenigsten umstritten als Spracherweiterungen, und sie bieten immer noch eine angemessene Menge an Benutzerfreundlichkeit.

Answer 2

Eigentlich ist es ganz einfach, sich selbst nicht überlappende Instanzen erfordern:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-} 

class Listifiable f a b where 
    listify :: f -> [a] -> b 

instance Listifiable b a b where 
    listify = const 

instance (Listifiable f) a b => Listifiable (a->f) a b where 
    listify f (x:xs) = listify (f x) xs 

Dann können Sie

GHCi> listify ((+) :: Int->Int->Int) [1,2 :: Int] :: Int 
3 

tun Aber die Notwendigkeit für die lokalen explizite Typsignaturen zeigt ganz die Probleme, die Sie‘

(Es könnte möglich sein, dieses Problem mit FunctionalDependencies zu lindern, aber zumindest nicht in einer direkten Art und Weise.)