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

[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

[lomeo.livejournal.com]

Ну ты маньяк!

lomeo: @pl \f g h x y -> f (g x) (h y)
lambdabot: ((flip . ((.) .)) .) . (.)

Хотя если бы я сокращал, то как нибудь так (думать неохота, но смысл, полагаю, ясен)

curry (uncurry f . (g *** h))

[deni-ok.livejournal.com]

Всё! Ура! Я, наконец, понял!
Понял почему здесь одним комбинатором B не обойтись, и откуда лезет C (flip)!

[lomeo.livejournal.com]

Нет, ты точно маньяк.

[deni-ok.livejournal.com]

Сироту всякий обидеть норовит :)

А flip лезет из очень простых соображений. Сравним

f(g(x y z)) = (.###) f g x y z
f (g x) (h y) = op??? f g h x y

В первом случае последовательность аргументов сохраняется. Во втором - нет.
Но (.) не умеет переставлять аргументы:

(.) a b c = a (b c)

Значит нужен ещё какой-то комбинатор, кроме B. Вроде так.

[lomeo.livejournal.com]

Да, это я сообразил :-)

[deni-ok.livejournal.com]

Мне для чего это понадобилось. Халявные теоремы очень легко считывать из коммутативных диаграммок:



Но для более сложных случаев тоже хочется оставаться на уровне стрелок, не привлекая аргументов типа xs, ys:



В последнем случае я не уверен, что это честная коммутативная диаграмма, но мне, как физику, пофиг: раз работает - в хозяйстве пригодится. Можно, конечно по-MLски: ([a],[a]) -> [a], но не хочется терять карринг :)

[lomeo.livejournal.com]

вроде, честная. Теперь увидел эту функцию, которую ты исследуешь. Без С комбинатора никак.

(ну ты разрисовал! как напишешь, дай почитать)

[deni-ok.livejournal.com]

> как напишешь, дай почитать

Не вопрос ;)

Вообще-то это слайды к следующему митингу SPbHUG.

[deni-ok.livejournal.com]

Читай на здоровье :)

[lomeo.livejournal.com]

Спасибо!!

[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]

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