How to write this polyvariadic composition function in Haskell?

Question

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

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

Context

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.

That's alright. If you want to, you could undelete your question and I'll post my answer there. After that, I can delete this question. — Aadit M Shah, Jan 31 '18 at 14:11
@ftor I wanted to share `const comp = run => Object.assign(g => comp(x => g(run(x))), {run})` — Mulan, Jan 31 '18 at 19:02
For others that are interested, this function is a derivative of a fun forward composition toy I made in [this answer](https://stackoverflow.com/a/46918344/633183) — Mulan, Jan 31 '18 at 19:03
@naomik I tried to get rid of the array and replace it with a purely functional computation. I really did. But I didn't recognize the pattern. And it was right in front of me! I just have the urgent feeling of learning. — , Jan 31 '18 at 19:51
@ftor you still did a really good job – it's really clever how the input array is built. I took a swing at [variadic comp](https://repl.it/@nakyoto/variadic-comp) and [variadic comp 2](https://repl.it/@nakyoto/variadic-comp-2) which is self-aware. I still think [fwd](https://repl.it/@nakyoto/forward-composition) makes more sense because `comp (f) (g) (h) .run (x)` isn't much better than `vcomp (f,g,h) (x)` – `comp (f) (g) (h)` and `vcomp (f, g, h)` are already independent of `x` — Mulan, Jan 31 '18 at 20:51

Aadit M Shah · Accepted Answer · 2018-02-01T03:41:25.277

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

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

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

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

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

Putting it all together:

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

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.

Edit: 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});

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)

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.

⁽¹⁾ 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.

your approach is way more elegant than https://hackage.haskell.org/package/control-dotdotdot-0.1.0.1/docs/Control-DotDotDot.html (even you need `run` at the end) good job! — phadej, Jan 31 '18 at 21:14
The whole development can also be done without GADTs with `newtype Comp a b = Comp { run :: a -> b }`. The `Comp` type is needed only to give a base case for the `Chain` instance resolution. — Daniel Wagner, Jan 31 '18 at 21:51
@phadej The `Control.DotDotDot` package doesn't do the same thing that I'm doing. It defines an operator that allows you to write functions like `\x y z -> g (f x y z)` as `g ... f` whereas you'd normally write it as `((g .) .) . f`. See: [What does (f .) . g mean in Haskell?](https://stackoverflow.com/q/20279306/783743) — Aadit M Shah, Feb 01 '18 at 04:05
@DanielWagner Indeed, the internal representation can simply be a function. I only created a GADT in order to stay faithful to the OP's original JavaScript code. — Aadit M Shah, Feb 01 '18 at 04:11

How to write this polyvariadic composition function in Haskell?

1 Answers1

Linked