Как нам посечь композицию: point-free на стероидах

[deniok]

На RSDN nikov последнее время пишет в point-free стиле на стероидах, используя конструкции имеющие "довольно ясный интуитивный смысл (c)". Типа

fpower = (appEndo.).(mconcat.).(.Endo).replicate

Поскольку я когда-то взвалил на себя ношу по несению point-free стиля в массы, придется писать мини-туториал.



Конструкция (. f) . g

\f g -> (. f) . g :: (d -> b) -> (a -> b -> c) -> (a -> d -> c)

Конструкция (. f) . g порождает функцию, эквивалентную g, только её второй аргумент вместо явной передачи заменен на результат вызова f.

g         :: a -> b -> c
f         :: d -> b
тогда
(. f) . g :: a -> d -> c

Диаграммой:

     d
    f|
     v
a -> b -> c
     g

В виде вызовов (с типами):

(g x::a (f z::d)::b)::c

Примеры:

-- перед отображением берем хвост списка
(. tail) . map
-- перед зиповкой увеличиваем элементы первого списка на 1
(. map succ) . zipWith
--перед свёрткой фильтруем список
(. filter (>3)) . foldr1
-- point-free определение replicate
(. repeat) . take

Конструкция (f .) . g

\f g -> (f .) . g :: (c -> d) -> (a -> b -> c) -> (a -> b -> d)

Конструкция (f .) . g порождает функцию, эквивалентную g, только её результат обрабатывается затем f.

g         :: a -> b -> c
f         :: d -> b
тогда
(f .) . g :: a -> b -> d

Диаграммой:

     g
a -> b -> c
          |f
          v
          d

В виде вызовов (с типами):

(f (g x::a y::b)::c)::d

Примеры:

-- point-free определение takeWhile
(fst .) . span
-- point-free определение mapM
(sequence .) . map
-- возвращает 0 при неудачном поиске
(fromMaybe 0 .) . find

Конструкция g . (f .)

\f g -> g . (f .) :: (d -> b) -> ((a -> b) -> c) -> ((a -> d) -> c)

Конструкция g . (f .) порождает функцию, эквивалентную g, только вместо ее функционального аргумента передается композиция f и нового функционального аргумента.

g         :: (a -> b) -> c
f         ::  d -> b
тогда
g . (f .) :: (a -> d) -> c

Диаграммой:

      d
     f|
      v
(a -> b) -> c
     g

В виде вызовов (с типами):

(g (f::d->b . h::a->d)::a->b)::c

Пример:

-- при отображении к передаваемой функции 
-- спереди прикомпозируется преобразование digitToInt
map . (digitToInt .)
-- при проверке видно, что succ вызывается 
-- до преобразования к Int (вылет на digitToInt 'G')
> (map . (digitToInt .)) succ "ABCDE"
[11,12,13,14,15]
> (map . (digitToInt .)) succ "ABCDEF"
[11,12,13,14,15,*** Exception: Char.digitToInt: not a digit 'G'

Конструкция g . (. f)

\f g -> g . (. f) :: (a -> d) -> ((a -> b) -> c) -> ((d -> b) -> c)

Конструкция g . (. f) порождает функцию, эквивалентную g, только вместо ее функционального аргумента передается композиция нового функционального аргумента и f.

g         :: (a -> b) -> c
f         ::  a -> d
тогда
g . (. f) :: (d -> b) -> c

Диаграммой:

     g
(a -> b) -> c
 |f
 v
 d

В виде вызовов (с типами):

(g (h::d->b . f::a->d)::a->b)::c

Пример:

-- при отображении к передаваемой функции 
-- сзади прикомпозируется преобразование digitToInt
map . (. digitToInt)
-- при проверке видно, что succ вызывается 
-- после преобразования к Int (нет вылета в отличие от прошлого примера)
> (map . (.digitToInt)) succ "ABCDE"
[11,12,13,14,15]
> (map . (.digitToInt)) succ "ABCDEF"
[11,12,13,14,15,16]

Comments

[antilamer.livejournal.com]

В последней секции должно быть Конструкция g . (. f)

[ivan-gandhi.livejournal.com]

Фигасе докуда прогресс дошел.

[kodt-rsdn.livejournal.com]

Проще было бы устроить раскрой брюк!
(((f.).g) x) y = (f.) (g x) y = (f.(g x)) y = f (g x y)
(((.f).g) x) y = (.f) (g x) y = ((g x).f) y = (g x) (f y)
((f.(g.)) x) y = f (g.x) y
((f.(.g)) x) y = f (x.g) y

Мне кажется, что можно пойти с другой стороны:
1) перечислить все формулы из 4 термов, из которых 2 связаны - и найти point-free записи для них
2) выучить самые расхожие формулы
3) в качестве образца расхожести можно взять вилки-ложки-крючочки из J

f g x y = (f g) x y
f g (x y) = ((f g).x) y = ((f g).) x y
f (g x) y = (f.g) x y
f (g x y) = (f.(g x)) y = ((f.).g) x y
f (g (x y)) = (f.(g.x)) y = ((f.).(g.)) x y

f x g y = (f x $ g) y = ($g) (f x) y = (($g).f) x y
f x (g y) = (f x . g) y = ((.g).f) x y
f (x g) y = f (x $ g) y = (f.($g)) x y
f (x g y) = ((f.)(x $ g)) y = ((f.).($g)) x y
f (x (g y)) = (f.x.g) y = ((f.).(.g)) x y

и т.д.
Очень несложно наловчиться - и рожать point-free с сечениями, и восстанавливать.

[ro-che.livejournal.com]

С одной стороны, да, изврат.
С другой -- фан :) Чуть больше примеров -- и уже тянет на статью в fprog или в Monad.Reader.

[lionet.livejournal.com]

Давай статью в fprog?

[helvegr.livejournal.com]

А оптимизатор догадывается произвести эти трансформации?

[migmit.vox.com (from livejournal.com)]

Про замечательную программу pointfree знаешь?

[lebenliebhaber.livejournal.com]

очень хороший пост

обязательно буду на него ссылаться, когда меня будут спрашивать, почему Хаскель нельзя тащить в продакшен (http://lebenliebhaber.livejournal.com/44901.html)