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

Question

如何在Haskell中定义Lisp的应用？不应该像Haskell这样的惰性语言允许这个定义，其中函数是curry？apply f [] = f apply f (x:xs) = apply (f x) xs它基本上是一个将给定函数应用于给定参数列表的函数，并且很容易在Lisp中完成。有没有解决方法？

Answer 1

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

用反射

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

import Data.Dynamicimport Data.Typeable

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

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

编辑：我无法想出一种方法来编写它，而不使用动态类型或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  = 32f True True False = 67f _ _ _ = 9tooMany = 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 = Znewtype 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 binstance Lift Z a b where
    type I Z a b = b
    lift _ b = Cons b tooManyinstance (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）