41

在像 Haskell 这样的函数被柯里化的惰性语言中不应该允许这个定义吗?

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

它基本上是一个将给定函数应用于给定参数列表的函数,例如在 Lisp 中很容易完成。有什么解决方法吗?

4

8 回答 8

23

很难给apply函数一个静态类型,因为它的类型取决于(可能是异构的)列表参数的类型。我能想到的在 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/existentials,我无法想出一种方法来编写它。很想看一个例子

于 2011-05-29T17:12:27.353 回答
13

我喜欢 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

然后引入用于提升的typeclass。您应该将类​​型读取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]
于 2011-06-09T19:51:03.923 回答
10

不,它不能。f并且f x是不同的类型。由于 haskell 的静态类型特性,它不能使用任何功能。它必须具有特定类型的功能。

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

于 2011-05-29T16:30:42.113 回答
7

这是在 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]
于 2011-05-30T10:14:55.273 回答
4

这段代码很好地说明了静态和动态类型检查之间的区别。使用静态类型检查,编译器无法确定是否apply f确实传递了f预期的参数,因此它会拒绝程序。在 lisp 中,检查是在运行时完成的,然后程序可能会失败。

于 2011-05-29T16:28:54.950 回答
1

我不确定这会有多大帮助,因为我在 F# 中编写此代码,但我认为这也可以在 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

在这种情况下,所讨论的“f”是使用允许递归数据类型定义的有区别的联合来定义的。这可以用来解决我猜提到的问题。

于 2011-05-30T04:55:28.610 回答
1

在其他一些人的帮助和输入下,我定义了一种方法来实现这一点(嗯,有点,使用自定义列表类型),这与以前的答案有点不同。这是一个老问题,但它似乎仍然被访问,所以我将添加完整的方法。

我们使用一个扩展(GADT),其列表类型有点类似于 Daniel Wagner 的,但使用的是标记函数类型而不是 Peano 编号。让我们逐段浏览代码。首先我们设置扩展名并定义列表类型。数据类型是多态的,因此在这个公式中,参数不必具有相同的类型。

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

让我们定义一个函数,它可以接受这样的列表并将其应用于函数。这里有一些类型技巧:函数有 type ,只有当这个类型与我们列表类型上的标签匹配时n,调用listApply才会编译。n通过不指定我们的输出类型o,我们在这方面留下了一些自由(在创建列表时,我们不必立即完全修复它可以应用于的函数类型)。

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

而已!我们现在可以将函数应用于存储在列表类型中的参数。期待更多?:)

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

不幸的是,我们有点被锁定在列表类型中,我们不能只转换普通列表以将它们与listApply. 我怀疑这是类型检查器的一个基本问题(类型最终取决于列表的值)但老实说我并不完全确定。

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

如果您对使用异构列表感到不舒服,您所要做的就是为LApp类型添加一个额外的参数,例如:

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

这里a表示参数类型,其中应用的函数也必须接受所有相同类型的参数。

于 2015-09-18T17:23:47.973 回答
0

这并不完全是您原始问题的答案,但我认为这可能是您的用例的答案。

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

list 的应用实例比这个超窄的用例要广泛得多......

λ>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"]

因此,确切地说,这不是同一个概念,而是很多组合用例,并添加了更多。

于 2017-05-05T01:10:52.153 回答