haskell - chain up elements with an associative binary operation

Question

I am an intermediate schemer, but only a haskell beginner. Here is my problem:

Suppose you have an associative binary operation, says (>>=). Is there a polyvariadic function p such that p (>>=) h g f e = h >>= g >>= f >>= e?

I am asking this question because this question says it is possible if the binary operation takes inputs of the same type. I wonder if this can be generalized.

EDIT-1: I try to modify the code in http://okmij.org/ftp/Haskell/vararg-fn.lhs (the section of Variable number of variably typed arguments) with little progress.

EDIT-2: Simplify the code a bit.

{-# LANGUAGE FunctionalDependencies, FlexibleInstances #-}


module Main where


class Lfold f a b | b -> a where 
  lfold :: (a -> (f a) -> (f a)) -> (f a) -> a -> b

instance Lfold f a (f a) where
  lfold op rid x = op x rid

instance Lfold f a b => Lfold f a (a -> b) where
  lfold op rid x y = lfold op (op x rid) y


test :: [String]
test = lfold (:) [] "a" "b" "c"

main :: IO ()
main = putStrLn $ show test

You mean you don't want `g`, `f` and `e` to be of the same type? — Bergi, Sep 17 '16 at 15:30
Yes, this should be possible, but you have to use some tricks for the type of the first parameter. Have you tried defining it? — Bergi, Sep 17 '16 at 15:32
@Bergi Yes, in such case, I cannot put them into a list and uses `foldr`. — Alex Vong, Sep 17 '16 at 15:32
He defined it for exactly 4 arguments; he's looking for a version that can take an arbitrary number of arguments. — chepner, Sep 17 '16 at 15:42
A better question, really, is why do you think you need a polyvariadic function? — chepner, Sep 17 '16 at 15:57

score 2 · Accepted Answer · edited May 23 '17 at 11:48

Yes, you can create such a function. It is very ugly however, and you will need to explicitly type every argument you are going to pass to make the compiler find the correct instance.

Starting from the polyvariadic function template you linked, I arrived at

{-# LANGUAGE FlexibleInstances, InstanceSigs, MultiParamTypeClasses #-}

class ImplicitChain m a r where
  p :: m a -> r

instance Monad m => ImplicitChain m a (m a) where
  p :: m a -> m a
  p x = x

instance (Monad m, ImplicitChain m b r) => ImplicitChain m a ((a -> m b) -> r) where
  p :: m a -> (a -> m b) -> r
  p x f = p (x >>= f)


h :: Int -> [Int]
h = replicate 2
g :: Int -> [Int]
g = (:[])
f :: Int -> [Int]
f = flip enumFromTo 2

test :: [Int]
test = p [1::Int] h g f

But you were asking whether we can do more generic, so that the binary operation is an argument as well. Yes:

{-# LANGUAGE FlexibleInstances, InstanceSigs, MultiParamTypeClasses, UndecidableInstances #-}

class ImplicitVariadic a b r where
  p :: (a -> b -> a) -> r

instance ImplicitVariadic a b (a -> a) where
  p :: (a -> b -> a) -> a -> a
  p _ x = x

instance (ImplicitVariadic a b (a -> r)) => ImplicitVariadic a b (a -> b -> r) where
  p :: (a -> b -> a) -> a -> b -> r
  p f x y = p f (f x y)

chepner · Answer 2 · 2016-09-17T15:56:23.607

You can't (at least, not easily), because you need to know how many arguments you are getting ahead of time. Because all functions in Haskell are automatically curried, every function takes exactly one argument and returns one value. Even a simple binary operator takes one argument (the first operand) and returns a function that takes one argument (the second operand) and returns a result. That is,

a + b == (+) a b
      == ((+) a) b

There is no way for your imaginary function p to know from its first argument how many other arguments are going to be given. That is, what should the type of p be?

p :: (a -> a -> a) -> a                -- zero arguments?
p :: (a -> a -> a) -> a -> a           -- one argument?
p :: (a -> a -> a) -> a -> a -> a      -- two arguments?
p :: (a -> a -> a) -> a -> a -> a -> a -- three arguments?

Instead, the best you can do is use a fold, which takes an operation and a list of operands.

foldr (+) 0 [h, g, f, e] == h + g + f + e + 0  -- explicit first argument of 0
foldr1 (+) [h, g, f, e] == h + g + f + e -- assumes a list of at least one value

To see what I mean by "not easily", look at the implementation of printf in the Text.Printf module. Even that is not a good example, because the first argument carries information (the number of placeholders in the format string) that a binary operation alone does not.

haskell - chain up elements with an associative binary operation

2 Answers2