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

Question

注意:这是作者删除的另一个问题的重新发布.这是原始问题:

---

我comp在Javascript中有这个polyvariadic 函数,并且想知道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中没有类型.我想这样的可变函数在其返回类型中必须是多态的.但是,到目前为止,这项任务超出了我的Haskell知识.任何线索都会有所帮助.

上下文

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

Answer 1

你是对的.您无法在Haskell ^(1)中构建可组合函数的异构列表.但是,您可以为可组合函数创建自己的列表数据类型,如下所示:

{-# 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模式创建一个多变量函数.为此,我们定义了一个类型类:

{-# 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调用.我们现在为这些定义实例:rComp 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作为其状态的链).我们最终可以comp像在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 b b c => c.要定义Chain我们需要类型的类MultiParamTypeClasses和FunctionalDependencies.要使用它我们需要FlexibleInstances.因此,您需要一个复杂的JavaScript运行时类型检查器才能正确键入检查comp.

编辑:正如naomik和Daniel Wagner在评论中指出的那样,您可以使用实际函数而不是可组合函数列表作为状态的内部表示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语言扩展才能c ~ c'在第一个实例中使用等式约束Chain.另外,正如您所看到的那样run g . f已经从定义转移run到了第二个实例中Chain.同样,id已经从定义转移run到了定义中comp.

⁽¹⁾您可以使用存在类型在Haskell中创建异构函数列表,但它们不具有可组合的附加约束.