deniok

Периодически жизнь возвращает меня к моей библиотеке композиторов. Её идея проста и в основном представляет не более чем упражнение для пытливого ума. Задача - выразить сложные композиции через единственный комбинатор (.). Например,


-- f(g(x y)) == (.##) f g x y
(.##) :: (a -> b) -> (c -> d -> a) -> c -> d -> b
(.##) = (.) . (.)

что позволяет устраивать point-free ралли,


concatMap = concat .## map

Текущая версия библиотеки


module Compose where

-- precedence and associativity analogous to (.)
infixr 9 .#, .##, .###, .####, .#####, .######

-- f(g(x y)) -- not point-free def
--compose'' :: (a -> b) -> (c -> d -> a) -> c -> d -> b
--compose'' f g x y = f(g x y)


addArity :: (a -> b -> c) -> (a -> (d -> b) -> (d -> c))
addArity =  (.) (.)

-- f(g(x)) -- stuff for comlectness
(.#) :: (a -> b) -> (c -> a) -> c -> b
(.#) =  (.) 

-- f(g(x y))
(.##) :: (a -> b) -> (c -> d -> a) -> c -> d -> b
(.##) = addArity (.#) -- (.) . (.)

-- f(g(x y z))
(.###) :: (a -> b) -> (c -> d -> e -> a) -> c -> d -> e -> b
(.###) = addArity (.##) -- (.) . (.##) 

-- f(g(x y z u))
(.####) :: (a -> b) -> (c -> d -> e -> f -> a) -> c -> d -> e -> f -> b
(.####) = addArity (.###) -- (.) . (.###)

-- f(g(x y z u v))
(.#####) :: (a -> b) -> (c -> d -> e -> f -> g -> a) -> c -> d -> e -> f -> g -> b
(.#####) = addArity (.####) -- (.) . (.####)

-- f(g(x y z u v w))
(.######) :: (a -> b) -> (c -> d -> e -> f -> g -> h -> a) -> c -> d -> e -> f -> g -> h -> b
(.######) = addArity (.#####) -- (.) .  (.#####)

--Unfortunately, a recursive definition of such recursion is impossible in Haskell :-(


-- f(g(h(x)))
compose3 :: (a -> b) -> (c -> a) -> (d -> c) -> d -> b
compose3 =  (.) .## (.)

-- f(g(h(i(x))))
compose4 :: (a -> b) -> (c -> a) -> (d -> c) -> (e -> d) -> e -> b
compose4 =  compose3 .## (.)

-- f(g(h(i(j(x)))))
compose5 :: (a -> b) -> (c -> a) -> (d -> c) -> (e -> d) -> (f -> e) -> f -> b
compose5 =  compose4 .## (.)

-- f(g(h(i(j(k(x))))))
compose6 :: (a -> b) -> (c -> a) -> (d -> c) -> (e -> d) -> (f -> e) -> (g -> f) -> g -> b
compose6 =  compose5 .## (.)

Сегодня по ходу дела мне потребовалась такая композиция


-- f (g x) (h y) = opUnknown f g h x y
opUnknown : :(a -> b-> c) -> (d -> a) -> (e -> b) -> d -> e -> c

У меня её нет :( В принципе можно написать генератор, который будет перебирать всё дерево композиций вширь, в надежде найти нужный тип. Но может кто справится усилием интеллекта? ;)

С использованием чего-то, кроме (.), не предлагать - сам умею.

UPD: Задача не имеет решения, спасибо