chain up elements with an associative binary operation

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 (>>=) hgfe = 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

---

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)

---

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.

链接地址: http://www.djcxy.com/p/43032.html

上一篇: 在Haskell的一个有序树中插入一个值

下一篇: 用关联二元运算链接元素