deniok: (typed lambda)
[personal profile] 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]


Date: 2009-10-16 01:29 pm (UTC)
From: [identity profile] antilamer.livejournal.com
В последней секции должно быть Конструкция g . (. f)

Date: 2009-10-16 01:32 pm (UTC)
From: [identity profile] deni-ok.livejournal.com
thnx
fxd

Date: 2009-10-16 05:09 pm (UTC)
From: [identity profile] ivan-gandhi.livejournal.com
Фигасе докуда прогресс дошел.

Date: 2009-10-16 05:17 pm (UTC)
From: [identity profile] deni-ok.livejournal.com
Большинство людей придерживается той мысли (вероятно довольно разумной), что такой код тяжело читать, при всей его экстраординарной лаконичности.

А мне нравится :)

Date: 2009-10-16 11:27 pm (UTC)
From: [identity profile] nponeccop.livejournal.com
Maintenance - это не только чтение, но и модификация. Если кто помнит, первые версии HN0 были поинтфри. Так я отказался от затеи, потому что было очень сложно модифицировать. Малые изменения в требованиях приводили к радикальному переписыванию.

Date: 2009-10-18 06:41 am (UTC)
From: [identity profile] ivan-gandhi.livejournal.com
Как раз лишнее выкинуто - и всегда можно подставить, мысленно прогоняя исполнение.

Date: 2009-10-16 05:14 pm (UTC)
From: [identity profile] 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 с сечениями, и восстанавливать.

Date: 2009-10-16 06:43 pm (UTC)
From: [identity profile] deni-ok.livejournal.com
> выучить самые расхожие формулы
Их слишком много, чтобы просто учить. Нужно порциями, да с примерами, иначе не запоминаются (у меня, по крайней мере).

Вот, скажем, логическая порция: тройная композиция унарных функций (f и g -- связанные функции, h -- свободная функция, x -- свободный аргумент):
f (g (h x)) = (f . (g . h)) x = ((f .) ((g .) h)) x = ((f .) . (g .)) h x

f (h (g x)) = (f . (h . g)) x = ((f .) ((. g) h)) x = ((f .) . (. g)) h x
f (h (g x)) = ((f . h) . g) x = ((. g) ((f .) h)) x = ((. g) . (f .)) h x

h (f (g x)) = ((h . f) . g) x = ((. g) ((. f) h)) x = ((. g) . (. f)) h x
Примеры (разумные) не придумываются :)

Date: 2009-10-16 08:37 pm (UTC)
From: [identity profile] ro-che.livejournal.com
С одной стороны, да, изврат.
С другой -- фан :) Чуть больше примеров -- и уже тянет на статью в fprog или в Monad.Reader.

Date: 2009-10-17 01:15 am (UTC)
From: [identity profile] lionet.livejournal.com
Давай статью в fprog?

Date: 2009-10-17 03:24 am (UTC)
From: [identity profile] lionet.livejournal.com
Напиши на ie@fprog.ru (issue editor) краткий план статьи, оттуда дёрнем.

Date: 2009-10-17 03:27 am (UTC)

Date: 2009-10-18 09:23 am (UTC)
From: [identity profile] helvegr.livejournal.com
А оптимизатор догадывается произвести эти трансформации?

Date: 2009-10-18 10:26 am (UTC)
From: [identity profile] deni-ok.livejournal.com
Ну сама по себе автоматизация этого - дело нехитрое (см. ниже по треду). Вот только насколько это полезно оптимизатору...

Date: 2009-10-18 10:50 am (UTC)
From: [identity profile] helvegr.livejournal.com
По идее, трансформация (. f) . g в g(x, f z) убирает ненужную partial application. Про @unpl я знаю, интересно было, работает ли это из коробки.

На моём маленьком примере работает:

Исходник:

g :: (a -> b) -> [a] -> [b]
g f l = map f (tail l)

h :: (a -> b) -> [a] -> [b]
h = (. tail) . map

Core:

h :: forall a_afx b_afy.
          (a_afx -> b_afy) -> [a_afx] -> [b_afy]

h =
  \ (@ a_afP)
    (@ b_afQ)
    (x_ayH :: a_afP -> b_afQ)
    (eta_syZ :: [a_afP]) ->
    map @ a_afP @ b_afQ x_ayH (tail @ a_afP eta_syZ)

g :: forall a_afA b_afB.
          (a_afA -> b_afB) -> [a_afA] -> [b_afB]
      
g =
  \ (@ a_agK)
    (@ b_agL)
    (f_afD :: a_agK -> b_agL)
    (l_afF :: [a_agK]) ->
    map @ a_agK @ b_agL f_afD (tail @ a_agK l_afF)


Как можно видеть, Core-представление обоих функций идентично.

Date: 2009-10-18 01:36 pm (UTC)
From: [identity profile] helvegr.livejournal.com
s/обоих/обеих/

Date: 2009-10-18 09:28 am (UTC)
From: [identity profile] migmit.vox.com (from livejournal.com)
Про замечательную программу pointfree знаешь?

Date: 2009-10-18 09:43 am (UTC)
From: [identity profile] migmit.vox.com (from livejournal.com)
MigMit:~ MigMit$ sudo cabal install pointfree

MigMit:~ MigMit$ pointfree 'iso (a, (b, c)) = ((a, b), c)'
iso = uncurry ((`ap` snd) . (. fst) . ((,) .) . (,))

Date: 2009-10-18 10:23 am (UTC)
From: [identity profile] deni-ok.livejournal.com
Ага, спасибо.

Вопрос в том, где начинается передозняк стероидов
> pointfree "\xs -> map succ (tail xs)"
map succ . tail
> pointfree "\f xs -> map f (tail xs)"
(. tail) . map
> pointfree "\t f xs -> map f (t xs)"
flip ((.) . map)
> pointfree "\m t f xs -> m f (t xs)"
flip . ((.) .)

Date: 2009-10-23 07:23 pm (UTC)
From: [identity profile] lebenliebhaber.livejournal.com
очень хороший пост

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

Date: 2009-10-23 07:39 pm (UTC)
From: [identity profile] deni-ok.livejournal.com
Ну и зря.
Это же чистая алгебра; и полно автоматических средств для "туда-сюда":
 > pl \x y -> x + 1
 const . (1 +)
 
 > unpl const . (1 +)
 (\ e _ -> 1 + e)
 
 > pl \v1 v2 -> sum (zipWith (*) v1 v2)
 (sum .) . zipWith (*)
 
 > unpl (sum .) . zipWith (*)
 (\ d g -> sum (zipWith (*) d g))
 
 > pl \x y z -> f (g x y z)
 ((f .) .) . g
 
 > unpl ((f .) .) . g
 (\ e j m -> f (g e j m))
 
 > pl \x y z -> f (g x y) z
 (f .) . g
 
 > unpl (f .) . g
 (\ d i -> f (g d i))
Можешь вделать в IDE "преобразовальщик под предпочтительный вид", если есть нужда ;-)

Date: 2009-10-23 07:43 pm (UTC)
From: [identity profile] lebenliebhaber.livejournal.com
я в принципе понимаю, как это устроено :-)

но когда я представляю себе встречю с такими штуками в модуле на три тысячи строк, написанном человеком, который пять лет как уволился - меня неиллюзорно бросает в дрожь :-)

Profile

deniok: (Default)
deniok

February 2022

S M T W T F S
  12345
6789101112
13141516171819
20212223 242526
2728     

Style Credit

Expand Cut Tags

No cut tags
Page generated Jun. 11th, 2025 02:41 pm
Powered by Dreamwidth Studios