Какой функциональный язык стоит изучать? - Декларативное программирование

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

D>Здравствуйте, R.K., Вы писали:

D>Класс. Компрехеншен — сила!

Есть такое.

D>A inits и tails — это будут
D>

D>tails [] = [[]]
D>tails xxs@(x:xs) = xxs:[ys | ys <- tails xs]

-- чуть проще, компрехеншн уже не нужен
tails [] = [[]]
tails xxs@(_:xs) = xxs : tails xs

Еще интересная задача сделать перестановки с учетом повторяющихся элементов. Функция perm' должна принимать на вход список списков, полученных от group(By) и возвращать список пермутаций без повторений. Например:

> perm' $ group "aabc"
["aabc","aacb","abac","abca","acab","acba","baac","baca","bcaa","caab","caba","cbaa"]

Здравствуйте, deniok, Вы писали:
D>А в python ленивость — через yield'ы?
Типа того.

Через yield'ы — генераторы, а ленивость — через них, т.к. вычисляется не весь список, а только затребованная часть.

... << RSDN@Home 1.2.0 alpha rev. 675>>

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

RK>Еще интересная задача сделать перестановки с учетом повторяющихся элементов. Функция perm' должна принимать на вход список списков, полученных от group(By) и возвращать список пермутаций без повторений. Например:
RK>

>> perm' $ group "aabc"
RK>["aabc","aacb","abac","abca","acab","acba","baac","baca","bcaa","caab","caba","cbaa"]
RK>

Не совсем понял про group — это множество всех (не?)упорядоченных подмножеств?
group "ab" даст ["","a","b","ab"]? Или ["","a","b","ab","ba"]?

Вообще решение в лоб — выкинуть повторяющиеся элементы, написав функцию uniq

uniq $ perm "aabc"

но оно, очевидно, не самое эффективное.
Вечером подумаю.

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

D>Не совсем понял про group — это множество всех (не?)упорядоченных подмножеств?
D>group "ab" даст ["","a","b","ab"]? Или ["","a","b","ab","ba"]?

inits, tails, group — все из модуля List. group выделяет соседние повторяющиеся элементы:

> group "aabc"
["aa","b","c"]
> :t group
group :: (Eq a) => [a] -> [[a]]
-- groupBy аналогична sortBy
> :t groupBy
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]

D>Вообще решение в лоб — выкинуть повторяющиеся элементы, написав функцию uniq
D>

D>uniq $ perm "aabc"
D>

Ага, и такая функция уже есть в List: nub

D>но оно, очевидно, не самое эффективное.

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

RK>inits, tails, group — все из модуля List. group выделяет соседние повторяющиеся элементы:
RK>Ага, и такая функция уже есть в List: nub

Ну серый я, как штаны пожарника. Мне казалось, что там из "разумного" только sort и zipы с большими номерами

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

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

C>>Причем, почему-то схемисты и лисповоды — самые ярые противники XML.

А>Так понятно почему. Из-за синтаксического оверхеда.

А>

А>(+ a b)
А>

А>vs.
А>

А><plus>
А>    <a />
А>    <b />
А></plus>

А>

Наверно жутко мучаешься когда вместо инфиксной записи операторов пишешь название функции перед списком аргументов (func x1 x2 x3)?

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

DC>Наверно жутко мучаешься когда вместо инфиксной записи операторов пишешь название функции перед списком аргументов (func x1 x2 x3)?

Да какие, блин, еще мучения. Что там такого мучительного-то?
Вообще же, хочу сказать, operator precedence parser — это максимум 10 строчек в виде макро и любые операторы с любыми приоритетами в результате, в отличие от "обычных" языков.
Только, разумеется, после некоторой практики, потребность в этом сама отпадает.
Во-первых, более-менее серьезное программирование — это не простые арифметические выражения и циклы. Это коллекции и их трансформации.
Ну типа возможность писать так ценнее всяких приоритетов:

> (map + '(1 2 3) '(4 5 6))
(5 7 9)

Ну и, конечно, префиксность любых функций позволяет разные мелкие вольности типа:

> (+ 1 2 3 4 5)
15

Примеры, для простоты, на Scheme

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

И чему тогда ты возражал?

Я просто хотел сказать, что оператор — это та же функция.

Ладно проехали.

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

D>Вообще решение в лоб — выкинуть повторяющиеся элементы, написав функцию uniq
D>

D>uniq $ perm "aabc"
D>

D>но оно, очевидно, не самое эффективное.
D>Вечером подумаю.

Вечер — понятие сильно растяжимое.

Такой день сегодня хороший. Выложу-ка я свое решение ниже.
Между прочим, задача очень практическая и нижепоследующая функция, только модифицированная для выдачи дерева Data.Tree вместо вложенных списков, крутится в моем решении Rectangle Strip Packing Problem.

-- perm' принимает список после group(By)
perm' [] = [[]]
perm' xs = intern' xs
    where
    intern' = concatMap (uncurry intern) . splits'
    intern [] [[q]] = [[q]]
    intern ps ((q:qs'):qs) = map (q:) $ intern' $ (ps++) $ case qs' of
        [] -> qs
        _ -> qs':qs

-- splits' это splits без последнего элемента
splits' xs@[_] = [([], xs)]
splits' xxs@(x:xs) = ([], xxs) : [(x:ps, qs) | (ps,qs) <- splits' xs]

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

RK>Вечер — понятие сильно растяжимое.

RK>

RK>-- perm' принимает список после group(By)
RK>perm' [] = [[]]
RK>perm' xs = intern' xs
RK>    where
RK>    intern' = concatMap (uncurry intern) . splits'
RK>    intern [] [[q]] = [[q]]
RK>    intern ps ((q:qs'):qs) = map (q:) $ intern' $ (ps++) $ case qs' of
RK>        [] -> qs
RK>        _ -> qs':qs

RK>-- splits' это splits без последнего элемента
RK>splits' xs@[_] = [([], xs)]
RK>splits' xxs@(x:xs) = ([], xxs) : [(x:ps, qs) | (ps,qs) <- splits' xs]
RK>

Вроде понял. intern, приняв, скажем ["a","b"] ["cc","d"], отщепляет первую c и гонит в начало, а остальное собираем в список и снова intern'. Назвать бы их (intern и intern') по-человечески. Вообще, механизм немного похож на мою версию permutations, которая с фильтрами. Там, где у меня была фильтрация, здесь — пересборка списка без q.

А splits' без последнего элемента — это чтобы в intern' образец ((q:qs'):qs) был неопровержим.

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

D>Вроде понял. intern, приняв, скажем ["a","b"] ["cc","d"], отщепляет первую c и гонит в начало, а остальное собираем в список и снова intern'. Назвать бы их (intern и intern') по-человечески. Вообще, механизм немного похож на мою версию permutations, которая с фильтрами. Там, где у меня была фильтрация, здесь — пересборка списка без q.

На все имен не напридумываешь. Эти же функции суть просто тело внешней, а имена им даны только для их рекурсивного вызова. Ну с фильтрами таки был лишний прогон с пересозданием списка во внутреннем цикле, а тут просто конкатенация — есть слабая надежда, что компилятор извернется и соптимизирует

Еще предикат в фильтре дает совершенно лишнее ограничение на Eq типа элементов списка.

D>А splits' без последнего элемента — это чтобы в intern' образец ((q:qs'):qs) был неопровержим.

Ну да, чтоб лишнего ветвления в паттернах интерн не было.

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

RK>На все имен не напридумываешь. Эти же функции суть просто тело внешней, а имена им даны только для их рекурсивного вызова. Ну с фильтрами таки был лишний прогон с пересозданием списка во внутреннем цикле, а тут просто конкатенация — есть слабая надежда, что компилятор извернется и соптимизирует

Еще предикат в фильтре дает совершенно лишнее ограничение на Eq типа элементов списка.

Понятно, что с фильтрами алгоритм дурной. Я просто перетаскивал на Хаскелл алгоритм из SICP.

Почему-то у меня никак не получается понять, как работает функция обращения списка с присаваинванием.
При попытке представить это у меня получается (d c d b c d a b c d), а вовсе не (a b c d).
Возможно я упускаю какую-то деталь, связанную с окружениями, или с тем как представляются списки (как мне показалось, в книге с представлением списков существует некоторый разброд).
Натолкните пожалуйста на верный путь.

(define (mystery x)
  (define (loop x y)
    (if (null? x)
        y
        (let ((temp (cdr x)))
          (set-cdr! x y)
          (loop temp x))))
  (loop x '()))

(define v (list 'a 'b 'c 'd))

(mystery v)

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

LS>

LS>(define (mystery x)
LS>  (define (loop x y)
LS>    (if (null? x)
LS>        y
LS>        (let ((temp (cdr x)))
LS>          (set-cdr! x y)
LS>          (loop temp x))))
LS>  (loop x '()))

LS>(define v (list 'a 'b 'c 'd))

LS>(mystery v)
LS>

В каждой итерации берётся голова первого списка и делается головой второго:
(let ((temp (cdr x))) — запоминаем хвост 1 списка
(set-cdr! x y) — голова 1 списка + 2 список
(loop temp x)))) — повторяем итерацию. При первом рекурсивном вызове: temp = (b c d), x = (a), для второго: temp = (c d), x = (b a) и т.д.

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

C>В каждой итерации берётся голова первого списка и делается головой второго:
C>(let ((temp (cdr x))) — запоминаем хвост 1 списка
C> (set-cdr! x y) — голова 1 списка + 2 список
C> (loop temp x)))) — повторяем итерацию. При первом рекурсивном вызове: temp = (b c d), x = (a), для второго: temp = (c d), x = (b a) и т.д.

Спасибо, я невнимательно отнесся к тому, что делает операция set-cdr!.

Во наобсуждали. Зашёл сюда случайно.
Сейчас в магазине есть книжка по Haskell на русском языке:

Душкин Р.В. Функциональное программирование на языке Haskell.

Кроме описания языка, там есть рассуждения о функциональном программировании.
Думаю, изучать ф.п. есть смысл из любопытства, а не в расчёте на последующее практическое
применение, которое было бы авантюрным решением.

	От:	deniok
	Дата:	18.03.07 08:30
	Оценка:

	От:	R.K.
	Дата:	18.03.07 09:41
	Оценка:	+1

От:	Tonal-	www.promsoft.ru
Дата:	18.03.07 10:05
Оценка:	1 (1)

	От:	deniok
	Дата:	18.03.07 10:05
	Оценка:

	От:	R.K.
	Дата:	18.03.07 10:19
	Оценка:

От:	dr.Chaos	Украшения HandMade
Дата:	21.03.07 11:40
Оценка:

	От:	Partisan
	Дата:	22.04.07 15:20
	Оценка: