10

这里仍然是 Haskell 新手。我知道足以让自己陷入错误假设的麻烦。如果我有以下功能...

quadsum w x y z = w+x+y+z

我想要一个可以接受列表的函数,将每个元素用作指定函数中的参数,例如quadsum,并返回一个柯里化函数供以后使用。

我一直在尝试一些效果...

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

希望能够做到这一点...

magicalFunctionMaker (quadsum) [4,3,2]

获得像...这样的咖喱函数:

(((quadsum 4) 3) 2)

或者,或者,调用:

magicalFunctionMaker (quadsum) [4,3,2,1]

导致...

((((quadsum 4) 3) 2) 1)

这可能吗?我被误导到什么程度?

4

6 回答 6

7

我认为您误解了 Haskell 类型系统。

首先,你的“quadsum”函数已经被柯里化了。您可以编写“quadsum 4 3”并返回一个期望 2 和 1 作为额外参数的函数。当你写“quadsum 4 3 2 1”时,它相当于“(((((quadsum 4) 3) 2) 1)”。

在 Haskell 中,整数列表的类型不同于整数或元组,例如“(4,3,2,1)”。鉴于此,很难理解您要做什么。如果你写这个应该会发生什么?

magicalFunctionMaker quadsum [5,4,3,2,1]

你的“magicalFunctionMaker”看起来很像“foldl”,除了你给 foldl 的函数只需要两个参数。所以你可以写:

mySum = foldl (+) 0

这将返回一个函数,该函数接受一个列表并对元素求和。

(顺便说一句,一旦你了解了这一点,就会了解 foldl 和 foldr 之间的区别。

编辑:

重新阅读您的问题后,我认为您正在尝试获得:

magicalFunctionMaker quadSum [4,3,2,1] :: Integer
magicalFunctionMaker quadSum [4,3,2] :: Integer -> Integer

这是不可能的,因为magicFunctionMaker 的类型取决于列表参数的长度,这意味着动态类型。正如有人所说,多变量函数可以做一些接近此的事情(尽管不是使用列表参数),但这需要相当多的类型骇客。

于 2010-09-23T07:38:00.033 回答
4

保罗约翰逊的回答几乎涵盖了它。做就是了

quadsum 4 3 2

结果将是您想要的功能,类型为Integer -> Integer

但有时这还不够好。有时您会得到数字列表,但您不知道列表有多长,您需要将元素应用到您的函数中。这有点难。你不能这样做:

magicalFunction2 f [] = f
magicalFunction2 f (x1:x2:xs) = f x1 x2

因为结果有不同的类型。在第一种情况下,结果需要两个参数,在第二种情况下,它是一个完全应用的函数,因此不允许更多参数。在这种情况下,最好的办法是保留列表和原始函数,直到有足够的参数可用:

type PAPFunc f a result = Either (f, [a]) result

magicfunc f xs = Left (f,xs)

apply (Left (f,xs)) ys = Left (f,xs++ys)
apply p _              = p

simp2 :: PAPFunc (a->a->b) a b -> PAPFunc (a->a->b) a b
simp2 (Left (f,(x1:x2:xs))) = Right (f x1 x2)
simp2 p = p

现在你可以这样做:

Main> let j = magicfunc (+) []
Main> let m = apply j [1]
Main> let n = apply m [2,3]

Main> either (const "unfinished") show $ simp2 m
"unfinished"
Main> either (const "unfinished") show $ simp2 n
"3"

您需要为每个 arity 提供一个单独的简化函数,这是 Template Haskell 最容易解决的问题。

在 Haskell 中使用参数列表(与列表的参数相反)往往非常尴尬,因为多个结果都有不同的类型,并且很少支持具有可变数量的不同类型参数的集合。我已经看到了三种一般类别的解决方案:

  1. 分别为每个案例显式编码(很快就会变成很多工作)。

  2. 模板 Haskell。

  3. 键入系统黑客。

我的回答主要是为了让 1 不那么痛苦。2和3不适合胆小的人。

编辑:事实证明,Hackage 上有一些 与此问题相关的软件包。使用“迭代”:

import qualified Data.Iteratee as It
import Control.Applicative

magic4 f = f <$> It.head <*> It.head <*> It.head <*> It.head

liftedQuadsum = magic4 quadsum
-- liftedQuadsum is an iteratee, which is essentially an accumulating function
-- for a list of data

Main> p <- It.enumChunk (It.Chunk [1]) liftedQuadsum
Main> It.run p
*** Exception: EofException
Main> q <- It.enumChunk (It.Chunk [2,3,4]) p
Main> It.run q
10

但是“iteratee”和“enumerator”可能有点矫枉过正。

于 2010-09-23T13:13:12.763 回答
3

我遇到了同样的问题:我有一个像

someFunc :: Int -> Int -> Int -> Int

我想做的是制作一个神奇的功能,例如

listApply :: [Int] -> (Int -> Int -> Int -> Int) -> Int

这样我可以说

listApply [1,2,3] someFunc

本能地,约翰的回答似乎同意,为了做到这一点,应该可以做一些类型系统的魔法。有一些类似问题的解决方案涉及使用一堆显式滚动和展开来显式地创建等递归数据类型(参见,例如,类型和编程语言的第 20 章,或此线程中的第 4 篇文章)。

我研究了一段时间的类型解决方案;感觉有可能,但在决定尝试 Template Haskell 之前,我并没有完全让它发挥作用,而且那里的事情要友好得多。

{-# LANGUAGE TemplateHaskell #-}    

import Language.Haskell.TH
import Language.Haskell.TH.Syntax

lApply :: [Int] -> String -> ExpQ
lApply    []  fn = return $ VarE (mkName fn)
lApply (l:ls) fn = [| $(lApply ls fn) l |]

(记得使用 LANGUAGE pragma 或 -XTemplateHaskell 命令行开关。)

要使用它,您可以在拼接中调用 lApply,如下所示:

> $(lApply [1,2] "+")
3

请注意,我必须使用包含我要调用的函数名称的字符串:我不能将函数直接提升到 ExpQ,但我可以引用它的全局绑定。我可以看到这可能会变得烦人。此外,由于我们遍历列表的方式,参数必须在列表中以相反的顺序呈现。

还有一些其他问题:为了将其推广到其他数据类型,这些类型必须在 Lift 类中具有相应的实例。例如,Double 没有实例,但您可以轻松地创建一个:

instance Lift Double where
        lift x = return $ LitE (RationalL (toRational x))

Lit 数据类型没有 DoubleL 构造函数,但可以使用 RationalL 代替它,因为它将拼接到 Fractional 类的一般成员。

如果您想将它与将混合类型作为参数的函数一起使用,您将无法传递列表,因为列表不能是混合类型。你可以使用元组来做到这一点,老实说,使用 Template Haskell 并不难。在这种情况下,您将创建一个函数来生成函数的 AST,该函数采用内部具有适当类型的元组并将其映射到所需的函数调用。或者,您可以将参数类型包装在适当制作的 ADT 中,顺便说一下,您也可以使用 Template Haskell 创建它。这留给读者作为练习:)

最后,所有标准模板 Haskell 限制都适用。例如,由于 GHC 阶段限制,您不能从定义它的模块调用此函数。

模板 Haskell 是有趣且有趣的东西,但老实说,iso-recursive 数据类型解决方案可能性能更高一些,并且显然不需要额外使用 TH。如果/当我开始工作时,我会回来并发布后续内容:)

于 2010-11-22T01:37:04.120 回答
2

您甚至无法“手动”列出不同长度的案例:

mf f [] = f
mf f [x] = f x
mf f [x,y] = f x y

--Occurs check: cannot construct the infinite type: t = t1 -> t
--Probable cause: `f' is applied to too many arguments
--In the expression: f x
--In the definition of `mf': mf f [x] = f x

这意味着 mf 不能采用任意“arity”的功能,您必须选择一个。出于同样的原因,您不能将任意列表转换为元组:您不能说元组将包含多少个元素,但类型系统需要知道。

通过使用“forall”将 f 限制为递归类型 a = a -> a 可能会有一个解决方案(参见http://www2.tcs.ifi.lmu.de/~abel/fomega/hm.html)。但是,我无法让它工作(似乎我必须告诉 Leksah 在某处使用标志 -XRankNTypes),并且对 f 的限制会使你的函数变得毫无用处。

[编辑]

想一想,最接近你想要的东西可能是某种 reduce 函数。正如 Paul 所指出的,这类似于 foldl、foldr ...(但下面的版本没有“额外参数”并且与 foldl 相比具有同质类型。请注意空列表缺少基本情况)

mf :: (a → a → a) -> [a] -> a
mf f [x] = x
mf f (x:y:xs) = mf f ((f x y) : xs)
于 2010-09-23T08:00:24.083 回答
1

我认为不会工作。(((quadsum 4) 3) 2)具有不同的类型Intger -> Integer,例如((((quadsum 4) 3) 2) 1),其类型为Integer.

于 2010-09-23T05:31:37.937 回答
1

我打算编辑我​​的另一篇文章,但这对于它自己来说已经足够大了。

这是使用“类型魔法”的一种方法,但在我看来它有点不理想,因为它需要一个特定于特定数量参数的函数的提升函数(更多下文)。

让我们从定义递归数据类型开始

data RecT a = RecR a
            | RecC (a -> RecT a)

因此,RecT 类型的变量可以只是一个包装结果 (RecR),也可以是一个持续递归 (RecC)。

现在,我们如何获取一些东西并将其转换为 Rect a 类型?

价值观很简单:

valRecT x = RecR x

RecR x 显然是 RecT a 类型。

一个接受一个参数的函数,比如 id 呢?

idRecT x = RecC $ \x -> RecR x

RecC 包装了一个函数,该函数接受一个变量并返回类型 RecT a。表达方式

\x -> RecR x

就是这样一个函数,因为我们之前观察到 RecR x 是 RecT a 类型。

更一般地,可以解除任何单参数函数:

lift1RecT :: (a -> a) -> RecT a
lift1RecT fn = RecC $ \a -> RecR $ fn a

我们可以通过在 RecC 中重复包装更深层嵌套的函数调用来概括这一点:

lift2RecT :: (a -> a -> a) -> RecT a
lift2RecT fn = RecC $ \b -> RecC $ \a -> RecR $ fn b a

lift3RecT :: (a -> a -> a -> a) -> RecT a
lift3RecT fn = RecC $ \c -> RecC $ \b -> RecC $ \a -> RecR $ fn c b a

好的,所以我们已经完成了所有这些工作,以将任意数量的参数的函数转换为单一类型,RecT a。我们如何使用它?

我们可以很容易地写出一层函数应用:

reduceRecT :: RecT a -> a -> RecT a
reduceRecT (RecC fn) = fn
reduceRecT  _        = undefined

换句话说,reduceRecT 接受一个类型为 RecT a 的参数和另一个类型为 a 的参数,并返回一个新的 RecT a ,它已经减少了一级。

我们还可以将 Rect 内的已完成计算展开到结果中:

unrollRecT :: RecT a -> a
unrollRecT (RecR fn) = fn
unrollRecT  _        = undefined

现在我们准备将参数列表应用于函数!

lApply :: [a] -> RecT a -> a
lApply    []  fn = unrollRecT fn
lApply (l:ls) fn = lApply ls $ (reduceRecT fn) l

让我们首先考虑基本情况:如果我们完成了计算,我们只需解开结果并返回它。在递归的情况下,我们将参数列表减少一,然后通过将列表的头部应用于减少的 fn 来转换 fn,从而产生一个新的 RecT a。

让我们试一试:

lApply [2,5] $ lift2RecT (**)
> 32.0

那么,这种方式的优缺点呢?嗯,Template Haskell 版本可以做部分列表应用;此处介绍的等递归类型解决方案并非如此(尽管我们原则上可以通过一些丑陋来解决此问题)。类型解决方案还有一个缺点是有更多的样板代码与之关联:我们需要一个 listNRecT 来表示我们想要使用的所有 N。最后,如果我们想应用于混合变量类型的函数,那么将其推广到类似的元组解决方案要容易得多。

当然,另一个有趣的可能性是通过使用 Template Haskell 生成 listNRecT 函数来增强简洁性;这消除了一些样板,但在某种意义上购买了两种实现的缺点。

于 2010-11-22T03:17:13.080 回答