Comment définir l'application de Lisp dans Haskell ?

Question

Cette définition ne devrait-elle pas être autorisée dans un langage paresseux comme Haskell dans lequel les fonctions sont curries ?

apply f [] = f
apply f (x:xs) = apply (f x) xs

Il s'agit essentiellement d'une fonction qui applique la fonction donnée à la liste d'arguments donnée, ce qui est très facile à réaliser en Lisp par exemple. Existe-t-il des solutions de rechange ?

Answer 1

Il est difficile de donner un type statique à l'élément apply puisque son type dépend du type de l'argument liste (éventuellement hétérogène). Il existe au moins deux voies une façon d'écrire cette fonction en Haskell à laquelle je peux penser :

Utiliser la réflexion

Nous pouvons reporter la vérification du type de l'application jusqu'au moment de l'exécution :

import Data.Dynamic
import Data.Typeable

apply :: Dynamic -> [Dynamic] -> Dynamic
apply f []      = f
apply f (x:xs)  = apply (f `dynApp` x) xs

Notez que le programme Haskell peut maintenant échouer avec une erreur de type au moment de l'exécution.

Via la récursivité de la classe de type

En utilisant la norme semi-standard Text.Printf (inventé par augustss, IIRC), une solution peut être codée. dans ce style (exercice). Cela n'est cependant pas très utile et nécessite encore une astuce pour cacher les types dans la liste.

Edit : Je n'ai pas trouvé de moyen d'écrire cela sans utiliser des types dynamiques ou des hlists/existentials. J'aimerais bien voir un exemple

Answer 2

J'apprécie la réponse de Sjoerd Visscher, mais les extensions -- en particulier IncoherentInstances Le système d'alerte, utilisé dans ce cas pour rendre possible une application partielle, peut être un peu décourageant. Voici une solution qui ne nécessite aucune extension.

Tout d'abord, nous définissons un type de données pour les fonctions qui savent ce qu'il faut faire avec un nombre quelconque d'arguments. Vous devriez lire a comme étant le "type d'argument", et b comme étant le "type de retour".

data ListF a b = Cons b (ListF a (a -> b))

Nous pouvons ensuite écrire des fonctions (Haskell) qui fusionnent ces fonctions (variadiques). J'utilise la fonction F pour toutes les fonctions qui se trouvent dans le prélude.

headF :: ListF a b -> b
headF (Cons b _) = b

mapF :: (b -> c) -> ListF a b -> ListF a c
mapF f (Cons v fs) = Cons (f v) (mapF (f.) fs)

partialApply :: ListF a b -> [a] -> ListF a b
partialApply fs          []     = fs
partialApply (Cons f fs) (x:xs) = partialApply (mapF ($x) fs) xs

apply :: ListF a b -> [a] -> b
apply f xs = headF (partialApply f xs)

Par exemple, le sum peut être considérée comme une fonction variadique :

sumF :: Num a => ListF a a
sumF = Cons 0 (mapF (+) sumF)

sumExample = apply sumF [3, 4, 5]

Toutefois, nous voulons également pouvoir traiter les fonctions normales, qui ne savent pas nécessairement quoi faire avec un nombre quelconque d'arguments. Alors, que faire ? Eh bien, comme en Lisp, nous pouvons lancer une exception au moment de l'exécution. Ci-dessous, nous utiliserons f comme exemple simple de fonction non variable.

f True True True  = 32
f True True False = 67
f _ _ _ = 9

tooMany = error "too many arguments"
tooFew  = error "too few arguments"
lift0 v = Cons v tooMany
lift1 f = Cons tooFew (lift0 f)
lift2 f = Cons tooFew (lift1 f)
lift3 f = Cons tooFew (lift2 f)

fF1 = lift3 f

fExample1 = apply fF1 [True, True, True]
fExample2 = apply fF1 [True, False]
fExample3 = apply (partialApply fF1 [True, False]) [False]

Bien entendu, si vous n'aimez pas la procédure de définition de lift0 , lift1 , lift2 , lift3 etc. séparément, vous devez activer certaines extensions. Mais vous pouvez aller très loin sans elles !

Voici comment vous pouvez généraliser à une seule personne. lift fonction. Tout d'abord, nous définissons quelques nombres standard au niveau du type :

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

data Z = Z
newtype S n = S n

Nous présentons ensuite la classe de type pour le levage. Vous devez lire le type I n a b comme " n copies de a comme arguments, puis un type de retour de b ".

class Lift n a b where
    type I n a b :: *
    lift :: n -> I n a b -> ListF a b

instance Lift Z a b where
    type I Z a b = b
    lift _ b = Cons b tooMany

instance (Lift n a (a -> b), I n a (a -> b) ~ (a -> I n a b)) => Lift (S n) a b where
    type I (S n) a b = a -> I n a b
    lift (S n) f = Cons tooFew (lift n f)

Et voici les exemples utilisant f de la version précédente, réécrite à l'aide de l'ascenseur généralisé :

fF2 = lift (S (S (S Z))) f

fExample4 = apply fF2 [True, True, True]
fExample5 = apply fF2 [True, False]
fExample6 = apply (partialApply fF2 [True, False]) [False]

Answer 3

Non, ce n'est pas possible. f y f x sont de différents types. En raison de la nature statiquement typée de haskell, il ne peut pas prendre n'importe quelle fonction. Elle doit prendre un type spécifique de fonction.

Supposons que f est transmis avec le type a -> b -> c . Ensuite f x a le type b -> c . Mais a -> b -> c doit avoir le même type que a -> b . Par conséquent, une fonction de type a -> (b -> c) doit être une fonction de type a -> b . Ainsi b doit être identique à b -> c qui est un type infini b -> b -> b -> ... -> c . Il ne peut pas exister. (continuer à remplacer b -> c para b )

Answer 4

Voici une façon de le faire en GHC. Vous aurez besoin de quelques annotations de type ici et là pour convaincre GHC que tout va bien se passer.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE IncoherentInstances #-}

class Apply f a r | f -> a r where
  apply :: f -> [a] -> r
instance Apply f a r => Apply (a -> f) a r where
  apply f (a:as) = apply (f a) as
instance Apply r a r where
  apply r _ = r

test = apply ((+) :: Int -> Int -> Int) [1::Int,2]

apply' :: (a -> a -> a) -> [a] -> a
apply' = apply

test' = apply' (+) [1,2]

Answer 5

Ce code illustre bien les différences entre le contrôle de type statique et dynamique. Avec le contrôle de type statique, le compilateur ne peut pas être sûr que apply f se voit réellement transmettre des arguments qui f attend, il rejette donc le programme. En Lisp, la vérification se fait au moment de l'exécution et le programme peut alors échouer.