haskell - связывает элементы с ассоциативной бинарной операцией

Я промежуточный интриган, но только начинающий на хаскеле. Вот моя проблема:

Предположим, у вас есть ассоциативная бинарная операция, говорит (>>=), Есть ли поливариадная функция p такой, что p (>>=) h g f e = h >>= g >>= f >>= e?

Я задаю этот вопрос, потому что этот вопрос говорит, что это возможно, если бинарная операция принимает входные данные одного типа. Интересно, можно ли это обобщить?

РЕДАКТИРОВАТЬ-1: Я пытаюсь изменить код в http://okmij.org/ftp/Haskell/vararg-fn.lhs (раздел Переменное число аргументов с переменной типизацией) с небольшим прогрессом.

РЕДАКТИРОВАТЬ-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
Источник

2 ответа

Решение

Да, вы можете создать такую ​​функцию. Однако это очень уродливо, и вам нужно будет явно вводить каждый аргумент, который вы собираетесь передать, чтобы компилятор нашел правильный экземпляр.

Начиная с шаблона поливариадной функции, который вы связали, я пришел к

{-# 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 автоматически каррируются, каждая функция принимает ровно один аргумент и возвращает одно значение. Даже простой бинарный оператор принимает один аргумент (первый операнд) и возвращает функцию, которая принимает один аргумент (второй операнд) и возвращает результат. То есть,

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?

Вместо этого лучшее, что вы можете сделать, это использовать фолд, который принимает операцию и список операндов.

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

Чтобы увидеть, что я имею в виду под "не легко", посмотрите на реализацию printf в модуле Text.Printf. Даже это не очень хороший пример, потому что первый аргумент содержит информацию (количество заполнителей в строке формата), которой нет в двоичной операции.

Источник
Другие вопросы по тегам