[Haskell] point-free - этюды - Декларативное программирование

Здравствуйте, deniok, Вы писали:

D>Активное использование point-free плюс конструкции
D>

D>-- для f :: a -> b
D>(f .) :: (c -> a) -> c -> b
D>(. f) :: (b -> c) -> a -> c
D>

Для меня эти конструкции имеют довольно ясный интуитивный смысл:

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

Здравствуйте, nikov, Вы писали:

N>

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

И это предельно понятная тебе запись?! Я чувствую себя таким крохотным по сравнению с твоей головой

Здравствуйте, Буравчик, Вы писали:

Б>

Б>import qualified Data.Map as M

Б>counts :: (Ord k) => [a] -> [(a, Int)]
Б>counts xs = M.toList $ M.fromListWith (+) $ zip xs (repeat 1)
Б>

counts = map (head &&& length) . group . sort

Здравствуйте, nikov, Вы писали:

N>Здравствуйте, Пельмешко, Вы писали:

П>>

П>>let fpower = Seq.init >> (>>) Const >> (<<) (Seq.fold (>>) id)
П>>

N>Мои варианты на Haskell:

N>

N>fpower = (foldr (.) id.).replicate
N>

N>или
N>

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

Это похоже на рождение нового стиля, nikov-style

Активное использование point-free плюс конструкции

-- для f :: a -> b
(f .) :: (c -> a) -> c -> b
(. f) :: (b -> c) -> a -> c

Здравствуйте, nikov, Вы писали:

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

Кстати, отсюда следует интересный вывод, что (f.) и (.h) коммутируют, то есть (f.).(.h) = (.h).(f.)

Здравствуйте, lomeo, Вы писали:

N>>

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

L>И это предельно понятная тебе запись?!

Просто я однажды объяснил себе, что такое (f.).g.
Если бы тип a -> a был моноидом, то возведение в степень было бы тривиально: размножить нужное число раз и выполнить mconcat. Но т.к. replicate принимает два аргумента, то это не просто mconcat.replicate, а (mconcat.).replicate. Но на самом деле функцию еще надо завернуть в Endo, а результат развернуть. Отсюда (appEndo.).(mconcat.).(.Endo).replicate

Здравствуйте, nikov, Вы писали:

N>Здравствуйте, nikov, Вы писали:

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

N>Кстати, отсюда следует интересный вывод, что (f.) и (.h) коммутируют, то есть (f.).(.h) = (.h).(f.)

И оба сводятся к тройной композиции с дыркой посередине \ g -> f . g . h

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

Здравствуйте, nikov, Вы писали:

Для меня этот код тоже малочитаемый

Поэтому решил задачки по-своему. Покритикуйте...

N>1) Написать функцию clone, которая повторяет каждый символ в строке (или в списке) заданное число раз. Например clone 2 "abc" должно дать "aabbcc".

clone xs = xs >>= replicate 2

N>2) Написать функцию power, которая повторяет строку (или список) заданное число раз. Например power 2 "abc" должно дать "abcabc".

power n xs = concat $ replicate n xs

N>3) Написать функцию fpower :: Int -> (a -> a) -> (a -> a), которая возводит функцию в указанную степень. Например fpower 3 (*2) должно вернуть функцию эквивалентную троекратному применению (*2), то есть (*2).(*2).(*2) или (*8).

fpower n fun = (!! n) . iterate fun

N>4) Написать функцию rotateLeft, которая производит циклическую перестановку элементов списка влево на указанное число позиций. Будет ли твой код работать, если список бесконечный? А если указанное число позиций больше, чем длина списка?

rotateLeft n xs = drop n xs ++ take n xs

Здравствуйте, nikov, Вы писали:

N>А функцию, которая работает только с конечными аргументами, можно написать гораздо короче.

Вот новый вариант.

vector :: Int -> [a] -> [[a]]
vector = replicateM

*Main> vector 2 "abcd"
["aa","ab","ac","ad","ba","bb","bc","bd","ca","cb","cc","cd","da","db","dc","dd"]

Пока не работает для бесконечных списков. Но зато как укоротил

... << RSDN@Home 1.2.0 alpha 4 rev. 1218>>

Здравствуйте, lomeo, Вы писали:

L>>>

L>>>enumerate = zipWith (map . (,)) [1..]
L>>>

МС>>Да, спасибо, это оно самое.
МС>>Попытался расписать типизацию на бумажке — чуть мозг не свернул

L>На самом деле ничего страшного здесь нет. Просто никогда так не пиши

А по-моему всё предельно понятно. Почему бы так не написать? Мне тоже сразу придумался именно этот код.

22.10.09 20:52: Ветка выделена из темы [Haskell] where в let ... in — Кодт

Здравствуйте, nikov, Вы писали:

N>А по-моему всё предельно понятно. Почему бы так не написать? Мне тоже сразу придумался именно этот код.

Ну для меня этот код пока что слабочитабелен. Haskell я начал изучать несколько дней назад.
Но запомню

Здравствуйте, Мишень-сан, Вы писали:

МС>Ну для меня этот код пока что слабочитабелен. Haskell я начал изучать несколько дней назад.

Ну тогда еще тренировочные задачки

1) Написать функцию clone, которая повторяет каждый символ в строке (или в списке) заданное число раз. Например clone 2 "abc" должно дать "aabbcc".
2) Написать функцию power, которая повторяет строку (или список) заданное число раз. Например power 2 "abc" должно дать "abcabc".
3) Написать функцию fpower :: Int -> (a -> a) -> (a -> a), которая возводит функцию в указанную степень. Например fpower 3 (*2) должно вернуть функцию эквивалентную троекратному применению (*2), то есть (*2).(*2).(*2) или (*8).
4) Написать функцию rotateLeft, которая производит циклическую перестановку элементов списка влево на указанное число позиций. Будет ли твой код работать, если список бесконечный? А если указанное число позиций больше, чем длина списка?
Попробуй написать в point-free style c использованием существующих комбинаторов.

Здравствуйте, nikov, Вы писали:

N>Ну тогда еще тренировочные задачки

N>3) Написать функцию fpower :: Int -> (a -> a) -> (a -> a), которая возводит функцию в указанную степень. Например fpower 3 (*2) должно вернуть функцию эквивалентную троекратному применению (*2), то есть (*2).(*2).(*2) или (*8).

Спасибо, nikov! Отлично голову поломал

Можно ли короче и более читабельно на F#?

let fpower = Seq.init >> (>>) Const >> (<<) (Seq.fold (>>) id)

Изначально было:

let fpower n f = Seq.init n (Const f) |> Seq.fold (>>) id

p.s. Я правильно понимаю, что в Хаскеле вместо << юзают flip (.)? Не нашёл в Prelude аналогичного << оператора...

Здравствуйте, nikov, Вы писали:

N>А по-моему всё предельно понятно. Почему бы так не написать? Мне тоже сразу придумался именно этот код.

Для тебя. Мне сложнее, смотри.

(map . (,))

Функция двух аргументов — композиция — функция двух аргументов. Да, понятно, т.к. использовал очень часто. Но не предельно, т.е. не интуитивно.
Поэтому стараюсь писать map (\x -> (i,x)), а так как количество вложенности лямбд превышает один уровень, то именую и выношу в where. Конечная запись кажется гораздо понятнее

go i = map $ (,) i

Всё это, разумеется, IMHO. Вот ещё одно IMHO: (,) мне кажется безобразным в этом случае. Когда появится сечение (i,) будет намного симпатичнее. А пока я пишу так:

go i = map $ \x -> (i,x)

Здравствуйте, Пельмешко, Вы писали:

П>Здравствуйте, nikov, Вы писали:

N>>Ну тогда еще тренировочные задачки

N>>3) Написать функцию fpower :: Int -> (a -> a) -> (a -> a), которая возводит функцию в указанную степень. Например fpower 3 (*2) должно вернуть функцию эквивалентную троекратному применению (*2), то есть (*2).(*2).(*2) или (*8).

П>Спасибо, nikov! Отлично голову поломал

П>Можно ли короче и более читабельно на F#?
П>

П>let fpower = Seq.init >> (>>) Const >> (<<) (Seq.fold (>>) id)
П>

Изначально было:
П>

П>let fpower n f = Seq.init n (Const f) |> Seq.fold (>>) id
П>

П>p.s. Я правильно понимаю, что в Хаскеле вместо << юзают flip (.)? Не нашёл в Prelude аналогичного << оператора...

fpower n f x = foldr ($) x $ replicate n f

Что делает (<<)? Если

x << f = f x

то это аналог flip ($), flip id ну и всё в таком духе. Например, через foldl моё решение можно было написать так

fpower n f x = foldl (\x -> ($ x)) x $ replicate n f

Здравствуйте, Пельмешко, Вы писали:

П>

П>let fpower = Seq.init >> (>>) Const >> (<<) (Seq.fold (>>) id)
П>

Мои варианты на Haskell:

fpower = (foldr (.) id.).replicate

или

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

Здравствуйте, nikov, Вы писали:

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

Узнаю азбуку Морзе!

Я бы в этом случае, скорее, воспользовался стрелками.

Здравствуйте, nikov, Вы писали:

N>Для меня эти конструкции имеют довольно ясный интуитивный смысл:

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

Вчера голову всю изломал чтобы сформулировать этот смысл, а всё так просто...

Эх, в ocaml страшнее выглядит:

(>>) f >> g
(<<) f >> g

Здравствуйте, nikov, Вы писали:

N>Ну тогда еще тренировочные задачки

Вот еще интересная задачка:
5) Написать функцию vector :: Int -> [a] -> [ [a] ], чтобы vector n xs давало всевозможные списки длиной n, у которых каждый элемент независимо пробегает значения из списка xs (вариант посложнее: функция vector должна работать, даже если xs — бесконечный список).

Здравствуйте, nikov, Вы писали:

N>чтобы vector n xs давало всевозможные списки длиной n, у которых каждый элемент независимо пробегает значения из списка xs

Другими словами, получить все строки длиной n в алфавите xs. Наверное, было бы лучше назвать функцию strings.

Здравствуйте, nikov, Вы писали:

N>5) Написать функцию vector :: Int -> [a] -> [ [a] ], чтобы vector n xs давало всевозможные списки длиной n, у которых каждый элемент независимо пробегает значения из списка xs (вариант посложнее: функция vector должна работать, даже если xs — бесконечный список).

vector 0 xs = [ [] ]
vector n xs = map (:) xs  `ap`  vector (n-1) xs

*Main> vector 2 "abc"
["aa","ab","ac","ba","bb","bc","ca","cb","cc"]
*Main> vector 2 "a"
["aa"]
*Main> take 15 $ vector 2 ['a'..]
["aa","ab","ac","ad","ae","af","ag","ah","ai","aj","ak","al","am","an","ao"]

Здравствуйте, Буравчик, Вы писали:

Б>

Б>vector 0 xs = [ [] ]
Б>vector n xs = map (:) xs  `ap`  vector (n-1) xs 
Б>

Этот вариант не работает с бесконечными списками, потому что следующий код никогда не выдаст [1,0]:

vector 2 [0 :: Integer ..]

А функцию, которая работает только с конечными аргументами, можно написать гораздо короче.

Здравствуйте, Буравчик, Вы писали:

N>>1) Написать функцию clone, которая повторяет каждый символ в строке (или в списке) заданное число раз. Например clone 2 "abc" должно дать "aabbcc".
Б>

clone xs = xs >>= replicate 2

Кажется, ты забыл принимать 2 в качестве параметра.
Я бы написал эту функцию

concatMap.replicate

N>>2) Написать функцию power, которая повторяет строку (или список) заданное число раз. Например power 2 "abc" должно дать "abcabc".
Б>

power n xs = concat $ replicate n xs

Это тоже самое, что

(concat.).replicate -- передаем 2 аргумента в replicate, а у результата вызываем concat

N>>3) Написать функцию fpower :: Int -> (a -> a) -> (a -> a), которая возводит функцию в указанную степень. Например fpower 3 (*2) должно вернуть функцию эквивалентную троекратному применению (*2), то есть (*2).(*2).(*2) или (*8).
Б>

fpower n fun = (!! n) . iterate fun

Очень хорошее решение.

N>>4) Написать функцию rotateLeft, которая производит циклическую перестановку элементов списка влево на указанное число позиций. Будет ли твой код работать, если список бесконечный? А если указанное число позиций больше, чем длина списка?
Б>

rotateLeft n xs = drop n xs ++ take n xs

Список не будет периодически прокручиваться при больших n.

Здравствуйте, nikov, Вы писали:

Ну и еще одна задачка:
6) Написать функцию tally :: Eq a => [a] -> [(a, Int)], которая подсчитает количество появлений каждого элемента в списке, одновременно удаляя дубликаты.

Здравствуйте, nikov, Вы писали:

N>Здравствуйте, nikov, Вы писали:

N>Ну и еще одна задачка:
N>6) Написать функцию tally :: Eq a => [a] -> [(a, Int)], которая подсчитает количество появлений каждого элемента в списке, одновременно удаляя дубликаты.

tally = uncurry (zipWith ($)) . (map (((head &&& length).) . filter . (==)) . nub &&& repeat)

Здравствуйте, VoidEx, Вы писали:

N>>6) Написать функцию tally :: Eq a => [a] -> [(a, Int)], которая подсчитает количество появлений каждого элемента в списке, одновременно удаляя дубликаты.

VE>

VE>tally = uncurry (zipWith ($)) . (map (((head &&& length).) . filter . (==)) . nub &&& repeat)
VE>

Мой вариант:

tally [] = []
tally (x:xs) = (x, 1 + length eqs) : tally neqs
  where (eqs, neqs) = partition (==x) xs

Здравствуйте, nikov, Вы писали:

N>6) Написать функцию tally :: Eq a => [a] -> [(a, Int)], которая подсчитает количество появлений каждого элемента в списке, одновременно удаляя дубликаты.

Я не понимаю, зачем использовать pointfree где попало?
Трудно читаем, трудно исправляем...

tally :: (Eq a) => [a] -> [(a, Int)]
tally xs = [ (key, length $ filter (==key) xs) | key <- nub xs ]

или более эффективно, но нужен Ord:

import qualified Data.Map as M

counts :: (Ord k) => [a] -> [(a, Int)]
counts xs = M.toList $ M.fromListWith (+) $ zip xs (repeat 1)

... << RSDN@Home 1.2.0 alpha 4 rev. 1218>>

Здравствуйте, nikov, Вы писали:

N>Мой вариант:
N>

N>tally [] = []
N>tally (x:xs) = (x, 1 + length eqs) : tally neqs
N>  where (eqs, neqs) = partition (==x) xs
N>

Мой вариант твоего варианта:

tally = map (head &&& length) . takeWhile (not . null) . unfoldr (Just . uncurry partition . ((==).head &&& id))

Здравствуйте, VoidEx, Вы писали:

VE>

VE>counts = map (head &&& length) . group . sort
VE>

Ну разве это не прекрасно?

Здравствуйте, VoidEx, Вы писали:

VE>

VE>counts = map (head &&& length) . group . sort
VE>

Согласен, так покрасивше.
Но! Памяти жрет раза в два больше и работает значительно дольше

Как-то понадобилась такая функция. Первая версия была именно такая, только без стрелок. Потом заменил на Map, стало лучше.

Теперь исправлю на такое

counts = M.toList . M.fromListWith (+) . map (id &&& const 1)

... << RSDN@Home 1.2.0 alpha 4 rev. 1218>>

Здравствуйте, Буравчик, Вы писали:

Б>Теперь исправлю на такое

counts = M.toList . M.fromListWith (+) . map (id &&& const 1)

Кстати. Из такого counts легко получаем сортировку, работающую часто быстрее, чем в стандартной библиотеке.

sort xs = concat [ replicate cnt key | (key,cnt) <- counts xs]

или (кому как нравится)

sort xs = counts xs >>= uncurry (flip replicate)

А также замена nub. В стандартной библиотеке сложность O(n^2). Здесь O(n log n).

nub xs = map fst $ counts xs

или

nub = map fst . counts

Но еще быстрее будет через Set:

nub xs = S.toList $ S.fromList xs

или так

nub = S.toList . S.fromList

Интересно, почему не использовали такие реализации.

... << RSDN@Home 1.2.0 alpha 4 rev. 1218>>

Здравствуйте, Буравчик, Вы писали:

Б>Пока не работает для бесконечных списков. Но зато как укоротил

Не очень элегантно, но короче не получилось. Работает и с бесконечными списками.

vector = (f.).replicate
  where
    f ((x:xs):xss) = map (x:) (f xss) `interleave` f (xs:xss)
    f [] = [[]]
    f _ = []

    interleave [] = id
    interleave (x:xs) = (x:).flip interleave xs

Здравствуйте, deniok, Вы писали:

D>Это похоже на рождение нового стиля, nikov-style

Я вот подумал — нельзя ли припахать какой-нибудь изящные рукодельные инфиксные комбинаторы, чтобы вместо лямбды (\x y z -> f x g y h z) навалять (f `_x` g `_y` h `_z`)?

... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, deniok, Вы писали:

D>>Это похоже на рождение нового стиля, nikov-style

К>Я вот подумал — нельзя ли припахать какой-нибудь изящные рукодельные инфиксные комбинаторы, чтобы вместо лямбды (\x y z -> f x g y h z) навалять (f `_x` g `_y` h `_z`)?

Боюсь сильно универсально не получится, из-за строгости типизации, но попробовать можно.

Здравствуйте, deniok, Вы писали:

К>>Я вот подумал — нельзя ли припахать какой-нибудь изящные рукодельные инфиксные комбинаторы
D>Боюсь сильно универсально не получится, из-за строгости типизации, но попробовать можно.

Нужно только подумать о базисе. Возможно, там будут нумерованные аналоги обоих комбинаторов — $ и . — что-нибудь типа %$, %$$, %$$$, %., %.., %...

Здравствуйте, Кодт, Вы писали:

К>Нужно только подумать о базисе. Возможно, там будут нумерованные аналоги обоих комбинаторов — $ и . — что-нибудь типа %$, %$$, %$$$, %., %.., %...

Второе рождение перла?

Здравствуйте, lomeo, Вы писали:

К>>Нужно только подумать о базисе. Возможно, там будут нумерованные аналоги обоих комбинаторов — $ и . — что-нибудь типа %$, %$$, %$$$, %., %.., %...

L>Второе рождение перла?

Типа того

... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>

Здравствуйте, nikov, Вы писали:

N>Ну тогда еще тренировочные задачки

Спасибо, неплохо голову поломал.
N>1) Написать функцию clone, которая повторяет каждый символ в строке (или в списке) заданное число раз. Например clone 2 "abc" должно дать "aabbcc".
Нужно получить clone :: Int->[Char]->[Char]
Есть replicate :: Int->a->[a]. Допустим, что есть такая f что f.replicate = clone . Тогда f :: (a->[a])->[a]->[a] — так это же concatMap (тут нам поможет hoogle). Получаем ответ:

clone = concatMap . replicate

N>2) Написать функцию power, которая повторяет строку (или список) заданное число раз. Например power 2 "abc" должно дать "abcabc".
Тут хочется скомбинировать уже зарекомендовавшего себя replicate и concat. Опять нужно получить f :: (String->[String])->String->String, или ([Char]->[Char]])->[Char]->[Char]. Это уже можно переписать как ([a]->[a]])->([a]->[a]). То есть нужно сконструировать функцию, которая принимает функцию вида [a]->[a]] и выдает функицю вида [a]->[a] использую concat для катенации полученного массива. Тут можно догадаться что такая функция — это (concat .) В итоге получаем:

power = ((concat.) . replicate)

N>3) Написать функцию fpower :: Int -> (a -> a) -> (a -> a), которая возводит функцию в указанную степень. Например fpower 3 (*2) должно вернуть функцию эквивалентную троекратному применению (*2), то есть (*2).(*2).(*2) или (*8).
Можно заметить, что эта задача похожа на предыдущую. Запишем сигнатуру так: fpower :: Int -> f ->f, причем заметим, что у нас есть операция concatf :: [f] -> f (композиция функций, concatf = foldr1 (.)) В этом случае нужно просто заменить concat из предыдущей задачи на наш concatf, и получим:

fpower = ((foldr1 (.)).) . replicate

PS Последний пример явно показывает, что писать код проще чем его читать. Написать это я смог, а вот прочитать — думаю что не смог бы.

Здравствуйте, nikov, Вы писали:

N>1) Написать функцию clone, которая повторяет каждый символ в строке (или в списке) заданное число раз. Например clone 2 "abc" должно дать "aabbcc".

clone = (id >=>) . replicate

N>2) Написать функцию power, которая повторяет строку (или список) заданное число раз. Например power 2 "abc" должно дать "abcabc".

power = (join.) . replicate

N>3) Написать функцию fpower :: Int -> (a -> a) -> (a -> a), которая возводит функцию в указанную степень. Например fpower 3 (*2) должно вернуть функцию эквивалентную троекратному применению (*2), то есть (*2).(*2).(*2) или (*8).

fpower = (foldl (.) id.) . replicate

N>4) Написать функцию rotateLeft, которая производит циклическую перестановку элементов списка влево на указанное число позиций. Будет ли твой код работать, если список бесконечный? А если указанное число позиций больше, чем длина списка?
N>Попробуй написать в point-free style c использованием существующих комбинаторов.

rotateLeft = foldl (.) id . flip replicate (uncurry (++) . (tail &&& return . head))

Здравствуйте, nikov, Вы писали:

N>Здравствуйте, nikov, Вы писали:

5) Написать функцию vector :: Int -> [a] -> [ [a] ], чтобы vector n xs давало всевозможные списки длиной n, у которых каждый элемент независимо пробегает значения из списка xs (вариант посложнее: функция vector должна работать, даже если xs — бесконечный список).

vector = (sequence .) . replicate

N>Ну и еще одна задачка:
N>6) Написать функцию tally :: Eq a => [a] -> [(a, Int)], которая подсчитает количество появлений каждого элемента в списке, одновременно удаляя дубликаты.

tally :: Eq a => [a] -> [(Int, a)]
tally = uncurry ($) . (last . (uncurry ((. tally) . (:)) . ((length &&& head) *** id) . (uncurry span) . ((==) . head &&& id) :) . (uncurry takeWhile) . (const . null &&& const [const []]) &&& id)

От:	nikov	http://www.linkedin.com/in/nikov
Дата:	16.10.09 08:41
Оценка:	20 (3)

От:	lomeo	http://lomeo.livejournal.com/
Дата:	16.10.09 08:44
Оценка:	+3

	От:	VoidEx
	Дата:	18.10.09 19:58
	Оценка:	47 (2)

	От:	deniok
	Дата:	16.10.09 08:34
	Оценка:

От:	nikov	http://www.linkedin.com/in/nikov
Дата:	16.10.09 08:59
Оценка:	21 (1)

	От:	Буравчик
	Дата:	17.10.09 22:00
	Оценка:	1 (1)

	От:	Мишень-сан
	Дата:	15.10.09 13:54
	Оценка:

От:	Пельмешко	blog
Дата:	16.10.09 08:02
Оценка:

От:	Oksana Gimmel	http://oksana-gimmel.blogspot.com/
Дата:	21.10.09 14:30
Оценка:

	От:	ettcat
	Дата:	25.10.09 08:32
	Оценка:

	От:	const_ptr
	Дата:	25.10.09 10:26
	Оценка:

	От:	const_ptr
	Дата:	25.10.09 16:57
	Оценка: