Come si definisce Lisp’s apply in Haskell?

Non dovrebbe essere consentita questa definizione in un linguaggio pigro come Haskell in cui le funzioni sono al curry?

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

È fondamentalmente una funzione che applica la funzione data alla lista di argomenti data ed è molto facile da fare in Lisp per esempio. Ci sono soluzioni alternative?

È difficile assegnare un tipo statico alla funzione apply , poiché il suo tipo dipende dal tipo dell’argomento (possibilmente eterogeneo) dell’elenco. Ci sono almeno due modi per scrivere questa funzione in Haskell a cui posso pensare:

Usando la riflessione

Possiamo rinviare il controllo del tipo dell’applicazione fino al runtime:

 import Data.Dynamic import Data.Typeable apply :: Dynamic -> [Dynamic] -> Dynamic apply f [] = f apply f (x:xs) = apply (f `dynApp` x) xs 

Si noti che ora il programma Haskell potrebbe non riuscire con un errore di tipo in fase di esecuzione.

Tramite la ricorsione della class di tipo

Usando il trucco semi-standard di Text.Printf (inventato da augustss, IIRC), una soluzione può essere codificata in questo stile (esercizio). Tuttavia, potrebbe non essere molto utile e richiede ancora qualche trucco per hide i tipi nell’elenco.

Modifica: non sono riuscito a trovare un modo per scrivere questo, senza utilizzare tipi dinamici o hliste / esistenziali. Mi piacerebbe vedere un esempio

Mi piace la risposta di Sjoerd Visscher, ma le estensioni – specialmente IncoherentInstances , utilizzate in questo caso per rendere ansible un’applicazione parziale – potrebbero essere un po ‘scoraggianti. Ecco una soluzione che non richiede alcuna estensione.

Innanzitutto, definiamo un tipo di funzione che sa cosa fare con un numero qualsiasi di argomenti. Dovresti leggere a qui come “tipo di argomento”, e b come “tipo di ritorno”.

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

Quindi possiamo scrivere alcune funzioni (Haskell) che definiscono queste funzioni (variadiche). Io uso il suffisso F per qualsiasi funzione che si trova nel Preludio.

 headF :: ListF ab -> b headF (Cons b _) = b mapF :: (b -> c) -> ListF ab -> ListF ac mapF f (Cons v fs) = Cons (fv) (mapF (f.) fs) partialApply :: ListF ab -> [a] -> ListF ab partialApply fs [] = fs partialApply (Cons f fs) (x:xs) = partialApply (mapF ($x) fs) xs apply :: ListF ab -> [a] -> b apply f xs = headF (partialApply f xs) 

Ad esempio, la funzione sum potrebbe essere pensata come una funzione variadica:

 sumF :: Num a => ListF aa sumF = Cons 0 (mapF (+) sumF) sumExample = apply sumF [3, 4, 5] 

Tuttavia, vogliamo anche essere in grado di gestire le normali funzioni, che non necessariamente sanno cosa fare con un numero qualsiasi di argomenti. Quindi che si fa? Bene, come Lisp, possiamo generare un’eccezione in fase di runtime. Sotto, useremo f come un semplice esempio di una funzione non-variadica.

 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] 

Ovviamente, se non ti piace il testo lift0 di definire lift0 , lift1 , lift2 , lift3 , ecc. lift3 , devi abilitare alcune estensioni. Ma puoi andare abbastanza lontano senza di loro!

Ecco come è ansible generalizzare a una singola funzione di lift . Per prima cosa, definiamo alcuni numeri di livello tipo standard:

 {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FlexibleContexts, TypeFamilies, UndecidableInstances #-} data Z = Z newtype S n = S n 

Quindi introdurre il typeclass per il sollevamento. Dovresti leggere il tipo I nab come ” n copie di a come argomenti, quindi un tipo di ritorno di b “.

 class Lift nab where type I nab :: * lift :: n -> I nab -> ListF ab instance Lift Z ab where type IZ ab = b lift _ b = Cons b tooMany instance (Lift na (a -> b), I na (a -> b) ~ (a -> I nab)) => Lift (S n) ab where type I (S n) ab = a -> I nab lift (S n) f = Cons tooFew (lift nf) 

Ed ecco gli esempi usando f da prima, riscritti usando l’ascensore generalizzato:

 fF2 = lift (S (S (SZ))) f fExample4 = apply fF2 [True, True, True] fExample5 = apply fF2 [True, False] fExample6 = apply (partialApply fF2 [True, False]) [False] 

No non può. f e fx sono diversi tipi. A causa della natura tipizzata staticamente di haskell, non può assumere alcuna funzione. Deve assumere un tipo specifico di funzione.

Supponiamo che f sia passato con type a -> b -> c . Quindi fx ha tipo b -> c . Ma a -> b -> c deve avere lo stesso tipo di a -> b . Quindi una funzione di tipo a -> (b -> c) deve essere una funzione di tipo a -> b . Quindi b deve essere uguale a b -> c , che è un tipo infinito b -> b -> b -> ... -> c . Non può esistere. (continua a sostituire b -> c per b )

Ecco un modo per farlo in GHC. Avrai bisogno di alcune annotazioni di tipo qua e là per convincere GHC che tutto funzionerà.

 {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE FunctionalDependencies #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE UndecidableInstances #-} {-# LANGUAGE IncoherentInstances #-} class Apply far | f -> ar where apply :: f -> [a] -> r instance Apply far => Apply (a -> f) ar where apply f (a:as) = apply (fa) as instance Apply rar where apply r _ = r test = apply ((+) :: Int -> Int -> Int) [1::Int,2] apply' :: (a -> a -> a) -> [a] -> a apply' = apply test' = apply' (+) [1,2] 

Questo codice è una buona illustrazione delle differenze tra il controllo di tipo statico e dinamico. Con il controllo di tipo statico, il compilatore non può essere sicuro che apply f davvero gli argomenti passati che f aspetta, quindi rifiuta il programma. In Lisp, il controllo viene eseguito in fase di esecuzione e il programma potrebbe non riuscire.

Non sono sicuro di quanto sarebbe utile se sto scrivendo questo in F # ma penso che questo possa essere fatto facilmente anche in Haskell:

 type 'a RecFunction = RecFunction of ('a -> 'a RecFunction) let rec apply (f: 'a RecFunction) (lst: 'a list) = match (lst,f) with | ([],_) -> f | ((x::xs), RecFunction z) -> apply (zx) xs 

In questo caso la “f” in questione viene definita utilizzando un’unione discriminata che consente la definizione del tipo di dati ricorsivo. Questo può essere usato per risolvere il problema menzionato, credo.

Con l’aiuto e l’input di alcuni altri ho definito un modo per ottenere questo risultato (beh, un po ‘, con un tipo di elenco personalizzato) che è leggermente diverso dalle risposte precedenti. Questa è una vecchia domanda, ma sembra essere ancora visitata quindi aggiungerò l’approccio per completezza.

Usiamo un’estensione (GADT), con un tipo di lista un po ‘simile a quello di Daniel Wagner, ma con un tipo di funzione di tagging piuttosto che un numero di Peano. Passiamo al codice in pezzi. Per prima cosa impostiamo l’estensione e definiamo il tipo di lista. Il tipo di dati è polimorfico, quindi in questo argomento di formulazione non è necessario avere lo stesso tipo.

 {-# LANGUAGE GADTs #-} -- n represents function type, o represents output type data LApp no where -- no arguments applied (function and output type are the same) End :: LApp oo -- intentional similarity to ($) (:$) :: a -> LApp mo -> LApp (a -> m) o infixr 5 :$ -- same as : 

Definiamo una funzione che può prendere una lista come questa e applicarla a una funzione. C’è qualche tipo di inganno qui: la funzione ha tipo n , una chiamata alla listApply compila solo se questo tipo corrisponde al tag n sul nostro tipo di lista. Lasciando il nostro tipo di output o non specificato, lasciamo un po ‘di libertà in questo (quando creiamo la lista non dobbiamo immediatamente correggere completamente il tipo di funzione a cui può essere applicato).

 -- the apply function listApply :: n -> LApp no -> o listApply fun End = fun listApply fun (p :$ l) = listApply (fun p) l 

Questo è tutto! Ora possiamo applicare funzioni agli argomenti memorizzati nel nostro tipo di lista. Previsto di più? 🙂

 -- showing off the power of AppL main = do print . listApply reverse $ "yrruC .B lleksaH" :$ End print . listApply (*) $ 1/2 :$ pi :$ End print . listApply ($) $ head :$ [1..] :$ End print $ listApply True End 

Purtroppo siamo un po ‘bloccati nel nostro tipo di lista, non possiamo semplicemente convertire le liste normali per usarle con listApply . Sospetto che questo sia un problema fondamentale con il controllo del tipo (i tipi finiscono a seconda del valore di un elenco) ma, a essere sinceri, non ne sono del tutto sicuro.

 -- Can't do this :( -- listApply (**) $ foldr (:$) End [2, 32] 

Se ti senti a disagio nell’usare una lista eterogenea, tutto ciò che devi fare è aggiungere un parametro extra al tipo LApp , ad esempio:

 -- Alternative definition -- data FList noa where -- Nil :: FList ooa -- Cons :: a -> FList foa -> FList (a -> f) oa 

Qui a rappresenta il tipo di argomento, in cui la funzione a cui si applica dovrà anche accettare argomenti dello stesso tipo.

Non sono sicuro del caso d’uso di questa funzione. Le liste sono immutabili e si applicano restituisce una funzione. Mi fa pensare che qualunque sia il tuo caso d’uso ci sarà una soluzione più diretta. Comunque posso suggerire un modo come segue;

 instance Show (a -> b) where show a = "function" apply :: Num a => (a -> a) -> [a] -> (a -> a) apply f [] = f apply f (x:xs) = apply ((\_ -> f) (fx)) xs 

Questa non è esattamente una risposta alla tua domanda iniziale, ma penso che potrebbe essere una risposta al tuo caso d’uso.

 pure f < *> [arg] < *> [arg2] ... -- example λ>pure (\abc -> (a*b)+c) < *> [2,4] < *> [3] < *> [1] [7,13] λ>pure (+) < *> [1] < *> [2] [3] 

L’istanza applicativa di lista è molto più ampia di questo caso d’uso super stretto però …

 λ>pure (+1) < *> [1..10] [2,3,4,5,6,7,8,9,10,11] -- Or, apply (+1) to items 1 through 10 and collect the results in a list λ>pure (+) < *> [1..5] < *> [1..5] [2,3,4,5,6,3,4,5,6,7,4,5,6,7,8,5,6,7,8,9,6,7,8,9,10] {- The applicative instance of list gives you every possible combination of elements from the lists provided, so that is every possible sum of pairs between one and five -} λ>pure (\abc -> (a*b)+c) < *> [2,4] < *> [4,3] < *> [1] [9,7,17,13] {- that's - 2*4+1, 2*3+1, 4*4+1, 4*3+1 Or, I am repeating argC when I call this function twice, but a and b are different -} λ>pure (\abc -> show (a*b) ++ c) < *> [1,2] < *> [3,4] < *> [" look mah, other types"] ["3 look mah, other types","4 look mah, other types","6 look mah, other types","8 look mah, other types"] 

Quindi non è lo stesso concetto, precisamente, ma molti di questi casi d’uso compositivi, e ne aggiunge altri.