如何在Haskell中定义Lisp的应用？

Question

不应该像Haskell这样的惰性语言允许这个定义,其中函数是curry？

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

它基本上是一个将给定函数应用于给定参数列表的函数,并且很容易在Lisp中完成.有没有解决方法？

Answer 1

很难给apply函数赋一个静态类型,因为它的类型取决于(可能是异构的)list参数的类型.在Haskell中编写此函数的方法至少有两种我能想到的方法:

用反射

我们可以推迟应用程序的类型检查直到运行时:

import Data.Dynamic
import Data.Typeable

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

请注意,现在Haskell程序可能会在运行时因类型错误而失败.

通过类型类递归

使用半标准Text.Printf技巧(由augustss,IIRC发明),可以用这种方式(练习)编码解决方案.虽然它可能不是很有用,但仍然需要一些技巧来隐藏列表中的类型.

编辑:我无法想出一种方法来编写它,而不使用动态类型或hlists /存在.很想看到一个例子

Answer 2

我喜欢Sjoerd Visscher的回复,但扩展 - 特别是IncoherentInstances在这种情况下用于部分应用的扩展- 可能有点令人生畏.这是一个不需要任何扩展的解决方案.

首先,我们定义一个函数的数据类型,知道如何处理任意数量的参数.你应该a在这里读作"参数类型",并b作为"返回类型".

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

然后我们可以编写一些(Haskell)函数来实现这些(可变参数)函数.我将F后缀用于恰好在Prelude中的任何函数.

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)

例如,该sum函数可以被认为是一个可变函数:

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

sumExample = apply sumF [3, 4, 5]

但是,我们还希望能够处理正常的函数,这些函数不一定知道如何处理任何数量的参数.那么该怎么办？好吧,就像Lisp一样,我们可以在运行时抛出异常.下面,我们将使用f非可变函数的简单示例.

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]

当然,如果你不喜欢定义的样板lift0,lift1,lift2,lift3,等分开,那么你就需要启用一些扩展.但是如果没有他们,你可以走得很远!

以下是如何推广到单个lift函数的方法.首先,我们定义一些标准的类型级数:

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

data Z = Z
newtype S n = S n

然后介绍用于提升的类型类.您应该将类​​型读I n a b作" 作为参数的n副本a,然后返回类型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)

以下是使用f之前使用广义电梯重写的示例:

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

不,它不能.f并且f x是不同的类型.由于haskell的静态类型性质,它不能承担任何功能.它必须采用特定类型的功能.

假设f传入类型a -> b -> c.然后f x有类型b -> c.但a -> b -> c必须具有相同的类型a -> b.因此,类型的函数a -> (b -> c)必须是类型的函数a -> b.所以b必须是相同的b -> c,这是一种无限类型b -> b -> b -> ... -> c.它不可能存在.(继续替代b -> c的b)

Answer 4

这是在GHC中实现这一目标的一种方法.你需要在这里和那里使用一些类型的注释来说服GHC这一切都会成功.

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