How to write this polyvarian compositional function in Haskell?

Question

Note: This is a report of another issue that the author deleted. Here is the original question:

---

I have this polyvarian comp function in Javascript, and I was wondering if a similar implementation in Haskell is possible. What interests me most is the comp 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 creates a heterogeneous array that usually has no type in Haskell. I suggest that such a variational function should be polymorphic in return type. However, this task far surpasses my knowledge of Haskell. Any key would be helpful.

Context

I am using Javascript runtime type checking so that I can build an array inside comp safe way. It requires explicit type annotations and supports only parametric and rank-2 polymorphism.

Answer 1

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

 {-# LANGUAGE GADTs #-} data Comp ab where Id :: Comp aa Comp :: Comp bc -> (a -> b) -> Comp ac run :: Comp ab -> a -> b run Id = id run (Comp gf) = run g . f 

The Id constructor is similar to [] , and the Comp constructor is similar to : but the arguments are inverted.

Next, we use the varargs template to create a multivariad function. To do this, define a class of type:

 {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-} class Chain abc | c -> a where chain :: Comp ab -> c 

Please note that our state is Comp bc , and our result is either Comp bc , or a function that takes another function as input (a -> b) and writes it with our state to create a new Chain called r with state Comp ac . Let the instances for them be defined now:

 {-# LANGUAGE FlexibleInstances #-} instance c ~ c' => Chain bc (Comp b c') where chain = id instance Chain acr => Chain bc ((a -> b) -> r) where chain gf = chain (Comp gf) comp :: Chain bbc => c comp = chain Id 

Now the Comp function can be defined as chain Id (i.e. a chain with an empty list Id as its state). Finally, we can use this Comp function, as it would in JavaScript:

 inc :: Int -> Int inc = (+1) sqr :: Int -> Int sqr x = x * x repeatStr :: String -> Int -> String repeatStr sx = concat (replicate xs) 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 ab where Id :: Comp aa Comp :: Comp bc -> (a -> b) -> Comp ac run :: Comp ab -> a -> b run Id = id run (Comp gf) = run g . f class Chain abc | c -> a where chain :: Comp ab -> c instance c ~ c' => Chain bc (Comp b c') where chain = id instance Chain acr => Chain bc ((a -> b) -> r) where chain gf = chain (Comp gf) comp :: Chain bbc => c comp = chain Id inc :: Int -> Int inc = (+1) sqr :: Int -> Int sqr x = x * x repeatStr :: String -> Int -> String repeatStr sx = concat (replicate xs) 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 bbc => c . To define a class of type Chain , we need MultiParamTypeClasses and FunctionalDependencies . To use it, we need FlexibleInstances . Therefore, to correctly enter the Comp check, you will need a complex JavaScript type runtime check.

---

Edit: As naomik and Daniel Wagner pointed out in the comments, you can use the actual function instead of the list of compound functions as your internal representation for the Comp state. 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 ab = Comp { run :: a -> b } class Chain abc | c -> a where chain :: Comp ab -> c instance c ~ c' => Chain bc (Comp b c') where chain = id instance Chain acr => Chain bc ((a -> b) -> r) where chain gf = chain (Comp (run g . f)) comp :: Chain bbc => c comp = chain (Comp id) 

Note that although we no longer use GADT, we still need the GADTs language GADTs to use the c ~ c' equality constraint in the first instance of Chain . Also, as you can see, run g . f run g . f was transferred from the definition of run to the second instance of Chain . Similarly, Id was transferred from the run definition to the Comp definition.

---

⁽¹⁾ You can use existential types to create a list of heterogeneous functions in Haskell, but they will not have an additional restriction on the ability to link.