如何在Haskell中编写这个polyvariadic组合函数？ [英] How to write this polyvariadic composition function in Haskell?

问题描述

注意：这是作者删除的其他问题的转贴。这是原始问题：

Note: This is a repost of another question, which the author deleted. Here's the original question:

我有这个polyvariadic comp 函数在Javascript中，我想知道Haskell中的类似实现是否可行。我最感兴趣的是 comp 的类型：

I have this polyvariadic comp function in Javascript and was wondering if a similar implementation in Haskell were possible. I am mostly interested in comp's type:

const comp = f => Object.assign(
  g => comp([g].concat(f)),
  {run: x => f.reduce((acc, h) => h(acc), x)}
);

const inc = n => n + 1;
const sqr = n => n * n;
const repeatStr = s => n => Array(n + 1).join(s);

comp(repeatStr("*")) (inc) (sqr).run(2); // "*****"

comp(repeatStr("*"))
  (inc)
  (inc)
  (inc)
  (inc)
  (inc).run(0); // "*****"

comp 构建一个通常在Haskell中没有类型的异构数组。我想这样的可变函数在其返回类型中必须是多态的。但是，到目前为止，这项任务超出了我的Haskell知识。任何线索都会有所帮助。

comp builds up a heterogeneous array that usually doesn't have a type in Haskell. I guess such a variadic function must be polymorphic in its return type. However, this task exceeds my Haskell knowledge by far. Any clue would be helpful.

上下文

我使用的是Javascript运行时类型检查器，以便我可以以类型安全的方式在 comp 中构建数组。它需要显式类型注释，并且仅支持参数和秩-2多态。

I use a Javascript runtime type checker so that I can build up the array inside comp in a type-safe manner. It requires explicit type annotations and supports only parametric and rank-2 polymorphism.

推荐答案

你是对的。您无法在Haskell ^（1）中构建可组合函数的异构列表。但是，您可以为可组合函数创建自己的列表数据类型，如下所示：

You're right. You can't build a heterogeneous list of composable functions in Haskell⁽¹⁾. However, you can create your own list data type for composable functions as follows:

{-# LANGUAGE GADTs #-}

data Comp a b where
    Id   :: Comp a a
    Comp :: Comp b c -> (a -> b) -> Comp a c

run :: Comp a b -> a -> b
run Id         = id
run (Comp g f) = run g . f

Id 构造函数类似于 [] 和 Comp 构造函数类似于：但是论点翻了。

The Id constructor is similar to [] and the Comp constructor is similar to : but with the arguments flipped.

接下来，我们使用 varargs pattern 创建一个polyvariadic函数。为此，我们定义了一个类型类：

Next, we use the varargs pattern to create a polyvariadic function. To do so, we define a type class:

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}

class Chain a b c | c -> a where
    chain :: Comp a b -> c

请注意，我们的州是 Comp bc 我们的结果是 Comp bc 或一个以另一个函数（a - > b）作为输入的函数并与我们的州合成，生成一个名为 r 的新链，状态为 Comp ac 。我们现在定义这些实例：

Note that our state is Comp b c and our result is either Comp b c or a function that takes another function (a -> b) as an input and composes it with our state to produce a new Chain called r with state Comp a c. Let's define instances for these now:

{-# LANGUAGE FlexibleInstances #-}

instance c ~ c' => Chain b c (Comp b c') where
    chain = id

instance Chain a c r => Chain b c ((a -> b) -> r) where
    chain g f = chain (Comp g f)

comp :: Chain b b c => c
comp = chain Id

comp 函数现在可以定义为 chain Id （即具有空列表 Id 作为其状态的链） 。我们最终可以像在JavaScript中一样使用这个 comp 函数：

The comp function can now be defined as chain Id (i.e. the chain with the empty list Id as its state). We can finally use this comp function as we'd do in JavaScript:

inc :: Int -> Int
inc = (+1)

sqr :: Int -> Int
sqr x = x * x

repeatStr :: String -> Int -> String
repeatStr s x = concat (replicate x s)

example1 :: String
example1 = comp (repeatStr "*") inc sqr `run` 2

example2 :: String
example2 = comp (repeatStr "*") inc inc inc inc inc `run` 0

全部放在一起：

{-# LANGUAGE GADTs, MultiParamTypeClasses, FunctionalDependencies,
             FlexibleInstances #-}

data Comp a b where
    Id   :: Comp a a
    Comp :: Comp b c -> (a -> b) -> Comp a c

run :: Comp a b -> a -> b
run Id         = id
run (Comp g f) = run g . f

class Chain a b c | c -> a where
    chain :: Comp a b -> c

instance c ~ c' => Chain b c (Comp b c') where
    chain = id

instance Chain a c r => Chain b c ((a -> b) -> r) where
    chain g f = chain (Comp g f)

comp :: Chain b b c => c
comp = chain Id

inc :: Int -> Int
inc = (+1)

sqr :: Int -> Int
sqr x = x * x

repeatStr :: String -> Int -> String
repeatStr s x = concat (replicate x s)

example1 :: String
example1 = comp (repeatStr "*") inc sqr `run` 2

example2 :: String
example2 = comp (repeatStr "*") inc inc inc inc inc `run` 0

如您所见， comp 的类型是 Chain bbc => ç。要定义 Chain 类型类，我们需要 MultiParamTypeClasses 和 FunctionalDependencies 。要使用它，我们需要 FlexibleInstances 。因此，您需要一个复杂的JavaScript运行时类型检查器才能正确键入check comp 。

As you can see, the type of comp is Chain b b c => c. To define the Chain type class we require MultiParamTypeClasses and FunctionalDependencies. To use it we require FlexibleInstances. Hence, you'll need a sophisticated JavaScript runtime type checker in order to correctly type check comp.

修改： naomik 和 Daniel Wagner 在评论中指出，您可以使用实际函数而不是可组合函数列表作为 comp 状态的内部表示。例如，在JavaScript中：

As naomik and Daniel Wagner pointed out in the comments, you can use an actual function instead of a list of composable functions as your internal representation for the state of comp. For example, in JavaScript:

const comp = run => Object.assign(g => comp(x => g(run(x))), {run});

同样，在Haskell中：

Similarly, in Haskell:

{-# LANGUAGE GADTs, MultiParamTypeClasses, FunctionalDependencies,
             FlexibleInstances #-}

newtype Comp a b = Comp { run :: a -> b }

class Chain a b c | c -> a where
    chain :: Comp a b -> c

instance c ~ c' => Chain b c (Comp b c') where
    chain = id

instance Chain a c r => Chain b c ((a -> b) -> r) where
    chain g f = chain (Comp (run g . f))

comp :: Chain b b c => c
comp = chain (Comp id)

请注意，即使我们不使用GADT我们仍然需要 GADTs 语言扩展，以便在第一个实例中使用等式约束 c~c' Chain 。另外，你可以看到运行g。 f 已从 run 的定义移至 Chain 的第二个实例。同样， id 已从 run 的定义移至 comp的定义。

Note that even though we don't use GADTs anymore we still require the GADTs language extension in order to use the equality constraint c ~ c' in the first instance of Chain. Also, as you can see run g . f has been moved from the definition of run into the second instance of Chain. Similarly, id has been moved from the definition of run into the definition of comp.

^（1）您可以使用存在类型创建Haskell中的异构函数列表，但它们没有可组合的附加约束。

⁽¹⁾ You can use existential types to create a list of heterogeneous functions in Haskell but they won't have the additional constraint of being composable.

这篇关于如何在Haskell中编写这个polyvariadic组合函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！