Разыскивается композитор

[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: Задача не имеет решения, спасибо lomeo, натолкнувшему на мысль.

Comments

[deni-ok.livejournal.com]

А решения с curry-uncurry медленнее чем чисто через (.). Мы с palm_mute полгода назад в чьём-то ЖЖ это обсуждали, а хозяин журнала гонял разные решения на скорость - моё выиграло :Ь

[lomeo.livejournal.com]

IMHO заинлайнится должно и тогда пофиг

[deni-ok.livejournal.com]

Да, согласен, ты, как всегда, прав :)

[lomeo.livejournal.com]

Как это я прав, если ты говоришь, что через композицию быстрее было? Может чтототам неинлайнится?

[deni-ok.livejournal.com]

Я неправильно вспомнил :) Там похоже всё в интерактивном режиме было, и смотрелось не быстродействие, а размер thunk'а:

http://rvp74.livejournal.com/46819.html

Можно у rvp74 подробности выяснить.

[lomeo.livejournal.com]

Ах, ну да, тема марсианских сисек раскрыта.

[deni-ok.livejournal.com]

Злой ты что-то сегодня :)

[lomeo.livejournal.com]

Чёрт я всего лишь пытался пошутить :)
На самом деле на этих выходных я переезжал, так что вполне возможно, что я не в себе.

[deni-ok.livejournal.com]

Можно поздравить с новосельем?

[lomeo.livejournal.com]

Ну... почти :-) Пока только я переехал, семью в среду перевезу.
Но вообще, ладно, уговорил - поздравляй!

[deni-ok.livejournal.com]

ПО-ЗДРА-ВЛЯ-Ю!
:-)