haskell - 使用关联二元运算链接元素
haskell - chain up elements with an associative binary operation
我是中级策划师,但haskell初学者。这是我的问题:
假设你有一个关联二元运算,说 (>>=)
。是否存在多元函数 p
使得 p (>>=) h g f e = h >>= g >>= f >>= e
?
我问这个问题是因为 this question 说如果二元运算采用相同类型的输入是可能的。我想知道这是否可以推广。
EDIT-1:我尝试修改 http://okmij.org/ftp/Haskell/vararg-fn.lhs 中的代码(可变类型参数的可变数量部分),但进展甚微。
EDIT-2:稍微简化代码。
{-# 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
你不能(至少,不容易),因为你需要提前知道有多少参数。因为 Haskell 中的所有函数都是自动柯里化的,所以每个函数只接受一个参数和 returns 一个值。即使是一个简单的二元运算符也接受一个参数(第一个操作数)和 returns 一个接受一个参数(第二个操作数)和 returns 结果的函数。也就是说,
a + b == (+) a b
== ((+) a) b
你的虚构函数 p
无法从它的第一个参数中知道将要给出多少个其他参数。即p
的类型应该是什么?
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?
相反,您可以做的最好的事情是使用折叠,它需要一个操作和一个 list 操作数。
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
要了解我所说的 "not easily" 的意思,请查看 Text.Printf 模块中 printf
的实现。即使这也不是一个很好的例子,因为第一个参数携带的信息(格式字符串中占位符的数量)是二进制运算本身所没有的。
是的,您可以创建这样的函数。然而,它非常丑陋,您需要显式键入要传递的每个参数,以使编译器找到正确的实例。
从你链接的the polyvariadic function template开始,我到达
{-# 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
但是你问的是我们能不能做的更通用一些,所以二元运算也是一个论点。是:
{-# 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)
我是中级策划师,但haskell初学者。这是我的问题:
假设你有一个关联二元运算,说 (>>=)
。是否存在多元函数 p
使得 p (>>=) h g f e = h >>= g >>= f >>= e
?
我问这个问题是因为 this question 说如果二元运算采用相同类型的输入是可能的。我想知道这是否可以推广。
EDIT-1:我尝试修改 http://okmij.org/ftp/Haskell/vararg-fn.lhs 中的代码(可变类型参数的可变数量部分),但进展甚微。
EDIT-2:稍微简化代码。
{-# 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
你不能(至少,不容易),因为你需要提前知道有多少参数。因为 Haskell 中的所有函数都是自动柯里化的,所以每个函数只接受一个参数和 returns 一个值。即使是一个简单的二元运算符也接受一个参数(第一个操作数)和 returns 一个接受一个参数(第二个操作数)和 returns 结果的函数。也就是说,
a + b == (+) a b
== ((+) a) b
你的虚构函数 p
无法从它的第一个参数中知道将要给出多少个其他参数。即p
的类型应该是什么?
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?
相反,您可以做的最好的事情是使用折叠,它需要一个操作和一个 list 操作数。
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
要了解我所说的 "not easily" 的意思,请查看 Text.Printf 模块中 printf
的实现。即使这也不是一个很好的例子,因为第一个参数携带的信息(格式字符串中占位符的数量)是二进制运算本身所没有的。
是的,您可以创建这样的函数。然而,它非常丑陋,您需要显式键入要传递的每个参数,以使编译器找到正确的实例。
从你链接的the polyvariadic function template开始,我到达
{-# 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
但是你问的是我们能不能做的更通用一些,所以二元运算也是一个论点。是:
{-# 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)