如何在Haskell中编写这个多元组合函数？

Question

注：这是another question的转贴，作者已删除。这是原始问题：

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

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中没有类型。我想这样的可变参数函数在其 return 类型中必须是多态的。但是，此任务远远超出了我的 Haskell 知识范围。任何线索都会有所帮助。

上下文

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

Answer 1

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

{-# 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 构造函数类似于 :，但参数翻转。

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

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}

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

请注意，我们的状态是 Comp b c，我们的结果是 Comp b c 或将另一个函数 (a -> b) 作为输入并将其与我们的状态组合以产生新的函数Chain 调用了 r，状态为 Comp a c。现在让我们为这些定义实例：

{-# 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 函数了

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 b b c => c。要定义 Chain 类型 class，我们需要 MultiParamTypeClasses 和 FunctionalDependencies。要使用它，我们需要 FlexibleInstances。因此，您需要一个复杂的 JavaScript 运行时类型检查器才能正确地进行类型检查 comp.

编辑： 正如 and 在评论中指出的那样，您可以使用实际函数而不是可组合函数列表作为状态的内部表示comp。例如，在 JavaScript:

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

同样，在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 语言扩展以便在 Chain 的第一个实例中使用等式约束 c ~ c'。此外，如您所见，run g . f 已从 run 的定义移至 Chain 的第二个实例中。同样，id 已从 run 的定义移动到 comp 的定义中。

⁽¹⁾ 您可以使用存在类型在 Haskell 中创建异构函数列表，但它们没有可组合的额外约束。

如何在Haskell中编写这个多元组合函数？

How to write this polyvariadic composition function in Haskell?

javascript

haskell

functional-programming

variadic-functions

function-composition