vale - que puedo hacer con haskell

¿Cómo puedo definir la aplicación de Lisp en Haskell?

Question

¿No debería permitirse esta definición en un lenguaje perezoso como Haskell en el que las funciones están al curry?

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

Básicamente es una función que aplica la función dada a la lista de argumentos dada y se hace muy fácilmente en Lisp, por ejemplo. ¿Hay alguna solución?

Answer 1

Con la ayuda y el aporte de algunos others , definí una forma de lograr esto (bueno, algo así como, con un tipo de lista personalizada) que es un poco diferente de las respuestas anteriores. Esta es una pregunta antigua, pero parece que aún se la visita, por lo que agregaré el enfoque para que esté completa.

Usamos una extensión (GADT), con un tipo de lista un poco similar a la de Daniel Wagner, pero con un tipo de función de etiquetado en lugar de un número de Peano. Repasemos el código en pedazos. Primero establecemos la extensión y definimos el tipo de lista. El tipo de datos es polimórfico, por lo que en esta formulación los argumentos no tienen que tener el mismo tipo.

{-# LANGUAGE GADTs #-}

-- n represents function type, o represents output type
data LApp n o where
  -- no arguments applied (function and output type are the same)
  End :: LApp o o
  -- intentional similarity to ($)
  (:$) :: a -> LApp m o -> LApp (a -> m) o

infixr 5 :$ -- same as :

Definamos una función que puede tomar una lista como esta y aplicarla a una función. Aquí hay algunos trucos: la función tiene tipo n , una llamada a listApply solo compilará si este tipo coincide con la etiqueta n en nuestro tipo de lista. Al dejar nuestro tipo de salida o no especificado, dejamos algo de libertad en esto (al crear la lista no tenemos que fijar de inmediato el tipo de función a la que se puede aplicar).

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

¡Eso es! Ahora podemos aplicar funciones a argumentos almacenados en nuestro tipo de lista. Esperado más? :)

-- 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

Lamentablemente, estamos encerrados en nuestro tipo de lista, no podemos simplemente convertir listas normales para usarlas con listApply . Sospecho que este es un problema fundamental con el verificador de tipos (los tipos terminan dependiendo del valor de una lista) pero para ser honesto, no estoy del todo seguro.

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

Si no se siente cómodo con el uso de una lista heterogénea, todo lo que tiene que hacer es agregar un parámetro adicional al tipo de LApp , por ejemplo:

-- Alternative definition
-- data FList n o a where
--   Nil :: FList o o a
--   Cons :: a -> FList f o a -> FList (a -> f) o a

Aquí a representa el tipo de argumento, donde la función a la que se aplica también tendrá que aceptar argumentos del mismo tipo.

Answer 2

Es difícil dar un tipo estático a la función apply , ya que su tipo depende del tipo del argumento de lista (posiblemente heterogéneo). Hay al menos dos formas de escribir esta función en Haskell que puedo pensar:

Usando la reflexión

Podemos diferir el control de tipos de la aplicación hasta el tiempo de ejecución:

import Data.Dynamic
import Data.Typeable

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

Tenga en cuenta que ahora el programa Haskell puede fallar con un error de tipo en el tiempo de ejecución.

Vía recursión de clase de tipo

Usando el truco Text.Printf semi-estándar (inventado por augustss, IIRC), una solución puede codificarse en este estilo (ejercicio). Sin embargo, puede que no sea muy útil y aún requiere algún truco para ocultar los tipos en la lista.

Editar: No pude encontrar una forma de escribir esto, sin usar tipos dinámicos o hlists / existenntials. Me encantaría ver un ejemplo

Answer 3

Esta es una forma de hacerlo en GHC. Necesitará algunas anotaciones de tipo aquí y allá para convencer a GHC de que todo va a funcionar.

{-# 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 4

Esta no es precisamente una respuesta a su pregunta original, pero creo que podría ser una respuesta a su caso de uso.

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

La instancia de aplicación de la lista es mucho más amplia que este caso de uso súper estrecho, aunque ...

λ>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 (/a b c -> (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 (/a b c -> 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"]

Entonces, no es el mismo concepto, precisamente, sino muchos de esos casos de uso de composición, y agrega algunos más.

Answer 5

Este código es una buena ilustración de las diferencias entre la comprobación de tipos estática y dinámica. Con la comprobación de tipos estática, el compilador no puede estar seguro de que la apply f realmente se está transmitiendo a los argumentos que espera, por lo que rechaza el programa. En lisp, la comprobación se realiza en tiempo de ejecución y el programa puede fallar.

Answer 6

Me gusta la respuesta de Sjoerd Visscher, pero las extensiones, especialmente IncoherentInstances , utilizadas en este caso para hacer posible la aplicación parcial, pueden ser un poco intimidantes. Aquí hay una solución que no requiere ninguna extensión.

Primero, definimos un tipo de datos de funciones que saben qué hacer con cualquier cantidad de argumentos. Debería leer aquí como el "tipo de argumento" b como el "tipo de retorno".

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

Entonces podemos escribir algunas funciones (Haskell) que rigen estas funciones (variadas). Uso el sufijo F para cualquier función que esté en el Preludio.

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)

Por ejemplo, la función sum podría considerarse como una función variadica:

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

sumExample = apply sumF [3, 4, 5]

Sin embargo, también queremos ser capaces de manejar funciones normales, que no necesariamente saben qué hacer con cualquier cantidad de argumentos. ¿Entonces lo que hay que hacer? Bueno, al igual que Lisp, podemos lanzar una excepción en tiempo de ejecución. A continuación, usaremos f como un ejemplo simple de una función no variada.

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]

Por supuesto, si no te gusta el texto estándar de definir lift0 , lift1 , lift2 , lift3 , etc. por separado, entonces debes habilitar algunas extensiones. ¡Pero puedes llegar bastante lejos sin ellos!

Aquí es cómo puede generalizar a una función de lift individual. Primero, definimos algunos números de nivel de tipo estándar:

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

data Z = Z
newtype S n = S n

Luego, introduce la clase de letra para levantar objetos. Debería leer el tipo I nab como " n copias de a como argumentos, luego un tipo de retorno 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)

Y aquí están los ejemplos usando f de antes, reescrito usando el levantamiento generalizado:

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 7

No estoy seguro de cuánto sería útil ya que estoy escribiendo esto en F # pero creo que esto también se puede hacer fácilmente en 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 (z x) xs

En este caso, la "f" en cuestión se define utilizando una unión discriminada que permite la definición recursiva del tipo de datos. Esto se puede usar para resolver el problema mencionado, supongo.

Answer 8

No estoy seguro del caso de uso de esta función. Las listas son inmutables y la aplicación devuelve una función. Me hace pensar que sea cual sea tu caso de uso, habrá una solución más directa para él. Sin embargo, puedo sugerir una manera de la siguiente manera;

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) (f x)) xs

Answer 9

No, no puede. f y fx son tipos diferentes. Debido a la naturaleza estáticamente tipada de haskell, no puede tomar ninguna función. Tiene que tomar un tipo específico de función.

Supongamos que f se pasa con tipo a -> b -> c . Entonces fx tiene tipo b -> c . Pero a -> b -> c debe tener el mismo tipo que a -> b . Por lo tanto, una función de tipo a -> (b -> c) debe ser una función del tipo a -> b . Entonces b debe ser lo mismo que b -> c , que es un tipo infinito b -> b -> b -> ... -> c . No puede existir. (continúa sustituyendo b -> c por b )