Node.js role for OUTSTANDING project (RTB, Big Data, Machine Learning)! Let’s talk today!

ФП: lazy evaluation — это завтрашние результаты вычисления функций уже сегодня.

После вводной статьи о ФП впору переходить к демонстрации конкретных примеров, приемов и трюков.

Сегодняшняя статья будет посвящена ленивым вычислениям (lazy evaluation). Оставайтесь с нами, и вы увидите, как функция может использовать в качестве аргумента результаты своей работы.

В качестве языка для иллюстрирования взят Haskell. От читателя не требуется знания Haskell или его синтаксиса.

Рассмотрим такую задачу: дан текст, в котором используются специальные слова @label и @ref. С помощью @label определяются метки, а с помощью @ref делаются ссылки на них. Например, так:

Введение@label{intro}. Как известно, чушь бывает разная: зеленая (@ref{green}) и красная (@ref{red}).
...
Как мы уже отмечали (@ref{intro}), чушь бывает разная, и именно поэтому жизненно важно ...
...
Чушь красная@label{red}.
Не следует путать с чушью зеленой (@ref{green}).
...
Чушь зеленая@label{green}.
Радикально отличается от чуши красной (@ref{red}).
...

Нам необходимо написать программу, которая заменит метки их номером (в виде «[1]», «[2]», ...), а ссылки — текстом «см. [1]». Из нашего образца должно получиться:

Введение[1]. Как известно, чушь бывает разная: зеленая (см. [2]) и красная (см. [3]).
...
Как мы уже отмечали (см. [1]), чушь бывает разная, и именно поэтому жизненно важно ...
...
Чушь красная[2].
Не следует путать с чушью зеленой (см. [3]).
...
Чушь зеленая[3].
Радикально отличается от чуши красной (см. [2]).
...

Классический алгоритм таков: проходим по тексту, собирая метки в порядке следования и назначая им номера. Проходим второй раз, заменяя метки и ссылки на вычисленые номера. Второй проход необходим, т.к. нам могут встретиться ссылки на метки, определенные дальше по тексту. Будем програмировать «сверху вниз»:

> module Main where
> import Data.List
> import Text.Regex.Posix
> import Control.Arrow
>
> main = do
>   txt <- readFile "sample.txt"
>   let numbering = collectLabels txt
>   let result = replaceLabels numbering txt
>   writeFile "sample.out" result

Тут txt, numbering и result - это не имена переменных, а имена, связанные (bound) с выражениями. Другими словами мы можем использовать numbering для того, чтобы быстро сослаться на результат применения функции collectLabels к выражению, связанному с именем txt. Можно связывать имена со значениями несколько раз, при этом более «вложенное» связывание перекрывает внешнее (как и в случае с именами локальных переменных в императивных языках программирования).

Поскольку мы идем «сверху вниз» и реализации collectLabels и replaceLabels у нас еще нет, так и напишем:

 > collectLabels = undefined
 > replaceLabels = undefined

Сохраняем наше творчество в файл «labeling.hs». Запускаем ghci (интерактивную среду, прилагающуюся к компилятору GHC), в появившемся промпте вбиваем «:load labeling.hs».

Ура, наша программа компилируется, хотя ничего разумного пока еще не делает. Мы еще не знаем, как именно будут реализованы функции collectLabels и replaceLabels, поэтому их тело состоит из одного примитива undefined. Использование undefined позволяет нам по ходу написания проверять правильность того, что мы пишем, начиная с самых первых строк. Как минимум, мы можем проверять, что компилятору удается выполнить вывод типов (type inference), т.е. определить, какой тип у всех выражений и функций, использованых в нашей программе, и проверить эти типы на соответствие друг другу (type checking).

Компиляторы C++/Java всегда выполняют проверку типов, но возможности вывода типов у них сильно ограничены. Упражнение номер один для пытливого читателя — написать минимальный компилирующийся «скелет», аналогичный приведеному, на C++/Java.

Начнем со сбора меток. Нам нужно найти в тексте все вхождения @label{xxx} в порядке упоминания и сложить их в какую-то структуру данных. Например, в список. Для извлечения текста используем сравнение с регулярным выражением:

> collectLabels txt =
>   let matches = ( txt =~ "@label\\\\{([^}]*)\\\\}" :: [[String]] )
>       in map (!!1) matches

Явно указывая тип возвращаемого значения для ф-ии (=~), мы заставляем библиотеку Text.Regex.Posix выбирать один из многих вариантов представления результата сравнения с регулярным выражением (всего их более 15-и). В данном случае нас интересует список [весь_текст_совпадения, текст_группы_1, текст_группы_2, ...] для каждого совпадения с образцом. Пример ожидаемого результата: [["@label{ccc}","ccc"],["@label{bbb}","bbb"]].

В каждом списке-результате нас интересует второй элемент — имя метки. Ф-ия извлечения элемента списка по номеру имеет имя (!!) - например, второй элемент списка lst можно получить выражением lst!!1. Поскольку нам надо применить операцию ко всем результатам, воспользуемся ф-ией map и приемом, называемым «частичное применение» (partial application или currying).

Чтобы этот кусок кода было проще понять, обратимся к ghci. Используем его для того, чтобы поиграться с кусками кода и лучше понять, что именно они делают:


<u>Можно просто проверить, совпала строка с регулярным выражением или нет</u> <b>*Main> "@label{aaa} some text @label{bbb} some more text" =~ "@label\\{([^}]*)\\}" :: Bool</b> True <u>... или получить полный текст всех совпадений</u> <b>*Main> "@label{aaa} some text @label{bbb} some more text" =~ "@label\\{([^}]*)\\}" :: [String]</b> ["@label{aaa}","@label{bbb}"] <u> ... или полный текст всех совпадений, плюс - текст всех подгрупп</u> <b>*Main> let matches = "@label{aaa} some text @label{bbb} some more text" =~ "@label\\{([^}]*)\\}" :: [[String]]</b> [["@label{aaa}","aaa"],["@label{bbb}","bbb"]] <u>... из которого потом можно извлечь либо текст совпадения</u> <b>*Main> map (!!0) matches</b> ["@label{aaa}","@label{bbb}"] <u> ... либо содержимое первой подгруппы.</u> <b>*Main> map (!!1) matches</b> ["aaa","bbb"] <u>Кроме того, мы можем посмотреть, что компилятор думает о типе определенного выражения:</u> <b>*Main> :type map (!!1)</b> map (!!1) :: [[a]] -> [a]

Если вы использовали функцию map в Perl, Python или Ruby, то знаете, что ей нужно давать функцию от одного аргумента. В то же время (!!) - это функция от двух аргументов (список и позиция_в_списке). Однако, если функции (!!) дать всего один аргумент, то в результате получится новая функция от одного аргумента. Это и есть частичное применение.

Особо обратите внимание на последний пример: используя информацию о том, что (!!) возвращает элемент списка, компилятор самостоятельно вычислил, что выражение-функция map (!!1) будет преобразовывать список списков в список просто значений. Самостоятельно посмотрите на тип функций map, (!!) и (!!1), чтобы понять, как именно компилятор произвел вывод. Подобный алгоритм выведения типов используется также в языках Clean, ML, OCaml, Scala, Nemerle, D. Ожидается, что вывод типов появится в C# 3.0 и Perl 6 (помните, что я говорил о влиянии ФП на mainstream языки?).

Как мы видим, функции не только могут быть использованы в качестве аргументов в вызовах функций, но и могут быть результатами вычисления выражений. В этом смысле функции ничем не отличаются от прочих базовых типов языка — чисел, символов, списков. Говорят, что функции являются полноправными сущностями (first-class citizens). В качестве упражнения номер два можете попробовать определить на C++/Java аналоги функций map и !! так, чтобы их можно было комбинировать в стиле map (!!1) и самостоятельно сделать вывод о том, являются ли функции полноправными сущностями в этих языках.

Проверим наш код:


<b>*Main> collectLabels "some text@label{one} with labels@label{two}\nand several lines@label{three}"</b> ["one","two","three"]

Быстро закрепим пройденый материал: мы увидели кусок программы на функциональном языке Haskell. Язык — со строгой типизацией (как в C++/Java), что не мешает существованию интерактивной среды исполнения (interactive top-level), как в Python. Для создания программы используется создание новых функций путем комбинирования библиотечных функций, и функций, определенных пользователем. Отсуствие изменяемых переменных (mutable variables) пока что сильно не мешает.

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

Нам нужно разделить исходный текст на строки, которые в свою очередь разбить на слова. Среди слов нам надо найти «специальные» и заменить их на номера, после чего собрать слова в строки, а строки — в текст. Так и запишем:

> replaceLabelsUgly labelList txt = unlines ( map unwords ( map (map process) ( map words ( lines txt ))))
>   where process = undefined

Люди, страдающие лиспофобией, уже бьются в припадке и хрипят «Скобки! Уберите скобки! Опять эти чертовы скобки! ». Пожалуй, они в чем-то правы. Перепишем эту функцию так:

> replaceLabelsBetter labelList txt = unlines $ map unwords $ map (map process) $ map words $ lines txt
>   where process = undefined

Уже лучше. «Прикольный синтаксический наворот» — скажут многие. Однако, это не выверт в синтаксисе языка. Тут использована функция ($), которая объявлена как инфиксный оператор и определена так:

f $ x = f x

Получается, что $ - это такой способ композиции функций, только и всего. И в самом деле, легко убедиться, что f (g x) = f $ g x. Можно даже взять и переписать функцию replaceLabels с использованием композиции функций в чистом виде:

> replaceLabelsPointfree labelList = unlines . map unwords . map (map process) . map words . lines
>   where process = undefined

Обратите внимание, что в этой форме записи у replaceLabelsPointfree стало на один аргумент меньше, как это и происходит в математической нотации. Мы пишем f(x) = ... и g(x) = ..., но t = f . g.

Впрочем, тут могут объявится любители Ruby и сказать «все равно эта функция записана криво и непонятно. Что за дела? Чтобы ее понять, надо читать ее с конца. То ли дело запись вида txt.to_lines().map({|l| l.words()}).map ..., которую можно нормально прочесть слева направо».

Что ж перепишем так, чтобы нормально читалось слева направо:

-> replaceLabels labelList = lines >>> map words >>> map (map process) >>> map unwords >>> unlines
->   where process = undefined

Как можно догадаться, (>>>) - это еще одна функция, позволяющая записать композицию ф-ий вот так, «шиворот навыворот», в виде, напоминающем shell pipes из Unix-а.

Ну, тут уже явно возмутятся даже те, кто честно пытался вникнуть в написанное без перенесения на Haskell опыта работы со своим любимым языком программирования. «И это называется нормально?» — скажут они. «Тут же нифига не понятно!».

Ну, раз непонятно, надо «мерять хвост частями» с помощью ghci:

<b>*Main> lines "this is a\nsample\nmultiline text"</b> ["this is a","sample","multiline text"] <b>*Main> lines >>> map words $ "this is a\nsample\nmultiline text"</b> [["this","is","a"],["sample"],["multiline","text"]] <b>*Main> lines >>> map words >>> map unwords $ "this is a\nsample\nmultiline text"</b> ["this is a","sample","multiline text"] <b>*Main> lines >>> map words >>> map unwords >>> unlines $ "this is a\nsample\nmultiline text"</b> "this is a\nsample\nmultiline text\n"

Теперь осталось разобраться с тем, что стоит между map words и map unwords. Если process w проверяет, не является ли слово w специальным, и заменяет его на номер, то map process ws выполнит эту операцию для всех слов в ws. Если ws - это список слов, стоявших в одной строке, то нам осталось применить эту операцию ко всем строкам текста, чтобы обработать его полностью. Для этого и нужен второй, внешний map. Получаем, что обработка все слов текста — это и есть map (map process).

Быстро закрепим пройденый материал: мы увидели, как возможность объявлять функции инфиксными операторами с нужным приоритетом позволяет гибко создавать новые управляющие конструкции языка и, фактически, создавать удобный нам синтаксис. Прослеживается типичный шаблон (pattern) програмирования на функциональных языках — создание «конвейера» из функций, последовательно применяющих к исходным данным ряд преобразований для получения конечного результата.

Нам осталось определить функцию process. Она должна работать следующим образом: все слова вида @label{xxx} заменять на «[номер метки xxx]», все слова @ref{xxx} заменять на «см. [номер метки xxx]», а все прочие слова — не трогать. С вашего позволения, я сразу приведу соответствующих код, без подробных объяснений.

> replaceLabels labelList = lines >>> map words >>> map (map process) >>> map unwords >>> unlines
>   where process w | isInfixOf "@label{" w = replace ""     w 
>                   | isInfixOf "@ref{"   w = replace "see " w
>                   | otherwise             = w
>
>         -- Эта функция заменяет ссылку/метку в слове `w' на ее [номер], предваряя [номер] строкой `prepend'
>         replace prepend w = 
>           -- Слово "Введение@label{aaaa}." будет разбито на части "Введение", "aaa" и ".",
>           -- из которых мы потом соберем результат.
>           let [[_,prefix,label,suffix]] = ( w =~ "(.*)@.*\\\\{([^}]*)\\\\}(.*)" :: [[String]] ) 
>               in prefix ++ prepend ++ "[" ++ idx label ++ "]" ++ suffix
>
>         -- Возвращает позицию `l' в списке `labelList' (нумерация начинается с 1).
>         idx l = case elemIndex l labelList of
>                      Just x  -> show (x+1)
>                      Nothing -> error $ "Label "++l++" is not defined"

Я надеюсь, что даже минимальный опыт работы с python и ruby позволит без особого напряжения прочесть и понять этот код. Возможно, вам также поможет пример функции, которая для четных аргументов возвращает «fuzz», а для нечетных — «buzz»:

fuzzbuzz x | even x    = "fuzz"
           | odd  x    = "buzz"
           | otherwise = "something is odd ..."

Проверим наш код:

<b>*Main> main</b>

В файле «sample.out» должен оказаться текст с замененными ссылками.

Тут самое время спросить: «НУ И ЧТО?». Казалось бы, до сих пор мы не сделали ничего необычного и отличающегося от того, что мы делали бы при программировании на любом другом императивном языке. Ну, разве что, обошлись без переменных :)

Наберитесь еще немного терпения, мы уже подобрались «гвоздю программы». Попробуем соединить сбор меток и замену ссылок в одну функцию. Предположим, что у нас уже есть полученый каким-то волшебным образом список всех меток в документе, назовем его allLabels. Откуда он взялся? А черт его знает. Допустим, мы сами прислали его себе из будущего, из того момента, когда мы уже обработали весь файл и знаем полный список меток :)

По-прежнему будем обрабатывать текст по словам, но чуть-чуть изменим алгоритм: если в слове есть ссылка, то использует allLabels для вычисления ее номера. Если же в слове есть метка, то используем allLabels для вычисления ее номера и добавим метку в список labelList. Зачем нам нужен labelList? Ну, должен же откуда-то взяться в будущем список меток, который мы пошлем себе в прошлое :)

Вашему вниманию предлагается функция process' (апостроф — это допустимый символ в имени функции), которая обрабатывает слово w, используя словарь меток allLabels и аккумулятор labelList, куда мы добавляем все найденые метки.

> process' (_,labelList,allLabels) w 
>   | isInfixOf "@label{" w = replace ""      True
>   | isInfixOf "@ref{"   w = replace "see "  False 
>   | otherwise             = (w, labelList, allLabels)
>   
>   -- Заменяем ссылку/метку в слове `w' на ее номер, предваряя его строкой `prepend'. Если `add' == True, 
>   -- добавляем метку в список labelList
>   where replace prepend add = 
>           let [[_,prefix,label,suffix]] = ( w =~ "(.*)@.*\\\\{([^}]*)\\\\}(.*)" :: [[String]] ) 
>               labelList' = if add then (label:labelList) else labelList
>             in (concat [prefix, prepend, "[", idx label,"]", suffix], labelList', allLabels)
>           
>         idx l = case elemIndex l allLabels of
>                      Just x  -> show (x+1)
>                      Nothing -> "Label "++l++" is not defined"

Кроме того, несколько изменим процесс обработки всего текста: вместо того, чтобы превращать его в список списков слов, превратим его в «плоский» список слов, который будет удобно обработать функций process'. Чтобы можно было собрать текст обратно, сохранив разбиение на слова, свяжем в с каждым словом номер строки, в которой оно (слово) стояло. После замены ссылоку/меток собирем слова в цельный текст, используя сохраненную информацию о том, какие слова были в какой строке.

> process = combineFromWords . replaceLabels . splitToWords
>   where
>   splitToWords txt = unzip $ concat $ zipWith tagWords [1..] $ lines txt
>   replaceLabels (tags, ws) = zip tags (processWords ws)
>   combineFromWords ws = unlines $ map (unwords . map snd) $ groupBy (comparing fst) ws
>   tagWords lineNo line = zip (repeat lineNo) (words line)
>   comparing f a b = (f a) == (f b)

Пару примеров для облегчения понимания этого куска (используйте ghci, чтобы увидеть типы и «попробовать на зуб» все функции, которые я не упомянул в этих примерах):

<b>*Main> zip [1..] $ lines "aaa bbb ccc\nddd eee fff"</b> [(1,"aaa bbb ccc"),(2,"ddd eee fff")] <b>*Main> let l = zipWith (\lineNo line -> zip (repeat lineNo) (words line)) [1..] $ lines "aaa bbb ccc\nddd eee fff"</b> [[(1,"aaa"),(1,"bbb"),(1,"ccc")],[(2,"ddd"),(2,"eee"),(2,"fff")]] <b>*Main> unzip $ concat l</b> ([1,1,1,2,2,2],["aaa","bbb","ccc","ddd","eee","fff"])

А теперь, собственно, создадим нашу «машину времени» — функцию, которая получит результаты работы функции process' (собраный списко меток) и «отправит его в прошлое» — передаст в качестве аргумента ... самой функции process'.

> processWords ws =
>   -- Из списка слов ["@label{aaa}","@ref{aaa}","ccc"] получаем список 
>   -- [ ("[0]",["aaa"],все_метки_из_будущего)
>   -- , ("см [0]", ["aaa"], все_метки_из_будущего)
>   -- , ("ccc", ["aaa"], все_метки_из_будущего)
>   -- ]
>   -- Нас интересует последий элемент этого списка, который содержит список всех найденых меток
>   let result = drop 1 $ scanl process' ([],[],reverse collectedLabels) ws
>       -- Извлекаем список найденых меток, чтобы использовать его ... 
>       -- ... в предыдущей строке в качестве аргумента для process' !
>       (_,collectedLabels,_) = last result
>       -- Конечным результатом является список обработаных слов, без информации о найденых метках.
>       in map discardLabelLists result
>   where discardLabelLists (w,_,_) = w

Чтобы проверить, что этот код действительно работает, изменим функцию main:

> main' = do
>   txt <- readFile "sample.txt"
>   writeFile "sample.out" $ process txt

Выполнив main', вы можете убедиться, что все метки и ссылки в действительности были заменены номерами. Черная магия? Отнюдь. Но как ...?

Использование в вычислениях еще не посчитаных значений становится возможным благодаря так называемой «ленивой» схеме вычислений (lazy evaluation) выражений в языках функционального программирования. При использовании этой схемы результатом выражения let y = ((f x) + (g x)) является не фактическая сумма, а что-то вроде ссылки на код, который эту сумму посчитает, когда нам понадобится значение y (я намерено опускаю технические детали). Если значение нам не понадобится — то и вычисление фактически не произойдет.

Таким образом, даже если вставить в произвольное место программы выражение let foobar = sum ( map (^2) [1..1000000000] ), можно не боятся, что программа будет тратить время на подсчет суммы квадратов всех чисел от одного до ста миллионов. Если мы нигде явно или косвенно не используем символ foobar, то это вычисление просто не произойдет.

Возвращаясь к нашему коду, становится понятно, что использование функции idx l не приводит к фактическому немедленному поиску метки l в списке allLabels. Вместо него создается «замороженный код» (thunk), который произведет этот поиск тогда, когда в нем будет необходимость. А необходимость эта появляется аж в самом конце программы, когда мы выводим результат обработки в выходной файл. Естественно, в этот момент времени у нас уже есть полный список меток, использованых в обрабатываемом тексте.

Получается, что я всех обманул — мы не отправляем «в прошлое» результаты вычислений, мы как бы «отправляем в будущее» сами вычисления с пометкой «до востребования».

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

Да, а чтобы вы не думали, что использованый мной прием — искуственный и редковстречающийся, вот вам еще практических примеров из этой же категории:

-- Функция `fib' возвращает список чисел Фибоначчи
fib = 1:1:(zipWith (+) fib (tail fib))

-- Функция `primes' возвращает список простых чисел
primes = primes' [2..]
  where primes' (n:ns) = n : primes' [ y | y <- ns, y `mod` n /= 0] 

-- Функция ralign выравнивает список строк вправо:
ralign xs = [ rjustify m x | x <- xs ]
  where
  m = maximum [ length x | x <- xs ]
  rjustify m x = replicate (m - length x) ' '  ++ x

Если эта статья вызовет интерес, то в следующих выпусках нашей программы ожидайте: работа с бесконечными списками и бесконечными структурами данных, зачем нужны в реальной жизни катаморфизмы (foldr) и анаморфизмы (unfoldr) списков и многое другое :)

PS
Текст этой статьи можно сохранить в файл с суффиксом «.lhs» (literate Haskell), и его можно будет без изменений загружать и исполнять в ghci как программу.

PPS
Ссылки для самостоятельного чтения:

  • Популярное

61 комментарий

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

Хорошая статья, в принципе все понялно вот эти строка меня просто убивает — не пойму что происходит) (_, collectedLabels, _) = last resultпоясните или ссылкните кто понимает

о, даже отступы почти получились. короче, для тех, кто будет еще код постить в комментах: используйте таг code, а в нем — nbsp везде вместо пробелов, плюс один nbsp в каждой пустой строке, чтобы не было совсем пустых строк, а то wordpress думает что это конец блока code. ща я совсем красивый код задвину:

 module Main where  import Text.Regex.Posix import qualified Data.Map as Map  data RefStatus = Resolved | Unresolved | Unused deriving (Eq, Show) type Dict = Map.Map String (Int, RefStatus)  main = getContents >>= (mapM_ putStr . process Map.empty)  process :: Dict -> String -> [String]  process dict "" =   [ "ERROR: " ++ show st ++ " " ++ name ++ " [" ++ show n ++ "]n"     | (name, (n, st)) <- Map.assocs dict, st /= Resolved ]  process dict txt =   pre : reftext : process newdict post   where (pre, _, post, match) =           txt =~ "(@(ref|label)\{([^}]+)\})" :: (String,String,String,[String])         (reftext, newdict) = lookupRef dict match  lookupRef dict [] = ("", dict)  lookupRef dict [_, st, name] =   mapFst (refText ref) $ Map.insertLookupWithKey updRef name (sz, ref) dict   where ref = if st == "ref" then Unresolved else Unused         sz = Map.size dict + 1         mapFst f (a, b) = (f a, b)         refText Unused     Nothing                = "[" ++ show sz ++ "]"         refText Unused     (Just (n, Unresolved)) = "[" ++ show n  ++ "]"         refText Unused     (Just (n, _))          = "[DUP: " ++ show n  ++ ":" ++ name ++ "]"         refText Unresolved Nothing                = "(see [" ++ show sz ++ "])"         refText Unresolved (Just (n, _))          = "(see [" ++ show n  ++ "])"         updRef _ (_, Unused)     (n, Unresolved)  = (n, Resolved)         updRef _ (_, Unused)     var              = var         updRef _ (_, Unresolved) (n, Unresolved)  = (n, Unresolved)         updRef _ (_, Unresolved) (n, _)           = (n, Resolved)

ну, у меня такое получилось — не самый короткий вариант, но зато O (n*log k) TIME, и все просто и понятно (я надеюсь):

 module Main where  import Text.Regex.Posix import qualified Data.Map as Map  data RefStatus = Resolved | Unresolved | Unused deriving (Eq, Show) type Dict = Map.Map String (Int, RefStatus)  main = getContents >>= (mapM_ putStr . process Map.empty)  process :: Dict -> String -> [String]  process dict "" =  [ "ERROR: " ++ show st ++ " " ++ name ++ " [" ++ show n ++ "]n"  | (name, (n, st)) <- Map.assocs dict, st /= Resolved ]  process dict txt =  pre : reftext : process newdict post  where (pre, _, post, match) =  txt =~ "(@(ref|label)\{([^}]+)\})" :: (String,String,String,[String])  (reftext, newdict) = lookupRef dict match  lookupRef dict [] = ("", dict)  lookupRef dict [_, st, name] =  mapFst (refText ref) $ Map.insertLookupWithKey updRef name (sz, ref) dict  where ref = if st == "ref" then Unresolved else Unused  sz = Map.size dict + 1  mapFst f (a, b) = (f a, b)  refText Unused Nothing = "[" ++ show sz ++ "]"  refText Unused (Just (n, Unresolved)) = "[" ++ show n ++ "]"  refText Unused (Just (n, _)) = "[DUP: " ++ show n ++ ":" ++ name ++ "]"  refText Unresolved Nothing = "(see [" ++ show sz ++ "])"  refText Unresolved (Just (n, _)) = "(see [" ++ show n ++ "])"  updRef _ (_, Unused) (n, Unresolved) = (n, Resolved)  updRef _ (_, Unused) val = val  updRef _ (_, Unresolved) (n, Unresolved) = (n, Unresolved)  updRef _ (_, Unresolved) (n, _) = (n, Resolved)

decorator: а вот, кстати, интересно на хаскеле в одну строку записать. только не так, как на питоне, а честно, т.е. как композицию функций. надо будет попробовать сегодня вечером, заодно и в Arrows поупражняюсь: -) ЗЫ во мы расписались, а! кайф какой: -)

2motus — это ж свободные полчаса надо. Найдуться — включу в примеры.

На форумк бага — кушает слова внутри <... >

2ili — да что было в 93 году я очень хорошо знаю;) Интересен прогресс за последние два года. [наверное все таки надо будет какой-то event попытаться сделать.] Еще я вижу в ваших постаз один «диссонанс»: > Поймите, сами статьи без работающей системы для применений никого не интересуют. (Точнее те, кто в этой области работает, и так всех знают и свежие статьи коллег просматривают, а кто нет — тому они нафиг здались) Интересуют как имепнно можно применить эти технолоогии и могут ли они в каких-то случаях удешевить разработку.

woops. how about nbsp indents (yuck):

  - line 1 (two spaces)   - line 1 (2 nbsp, 2 regular spaces)

let’s see how the code posting works:

-- 2 spaces indent iside the <code&gt block -- 4 spaces after an empty line..

end of code block — 2 spaces indent inside the <pre&gt block — 4 spaces after an empty line..end of pre block

-- 2 spaces indent inside the <code&gt + <pre&gt block -- 4 spaces after an empty line..

end of pre block embedded in code block...the code is coming soon...

господа, я что-то совсем запутался — мы все еще lazy evaluation обсуждаем? насколько я понимаю, term rewriting это вообще отдельный раздел науки, который к ФП имеет очень косвенное отношение. т.е. я не спорю, что все это и здорово, и полезно, и Turing complete, но тем не менее...а вот кстати! задание любителям term rewriting, а равно и всем остальным — напишите в вашей любимой системе (Stratego, APLAN, whatever) программу для нумерации @ref {} и @label {}. серьезно, давайте сделаем наш mini-shootout! программа на питоне у нас уже есть, целых две, на хаскеле тоже... я вот свою сегодня вечерком нацарапаю, и посмотрим, тем более что askel давно интересуется, насколько это все практично (см. коммент 37).слабо?: -) ЗЫ меня ногами не бить, я еще учусь, но конструктивные комментарии приветствуются! ЗЗЫ консерваторы, тоже подключайтесь! слабо на джаве или на С++ написать — так, чтобы было короче, чем на питоне?

Был в Киеве пару лет назад интересный workshop http://www.imath.kiev.ua/~scem.../а в 93 был ISSAC...Из того что было пару лет назад рекомендую http://www.imath.kiev.ua/~scem... — кстати, Виктор сам вроде из Киева)

Да. Интересно. Кстати, а может выделить какие-то выходные, сделать неформальный workshop по применению функционального программирования в Киеве (?) Заодно и вводную презентацию сделаете такую, что бы NDA не нарушало. Насколько я помню, по расказе о самом языке у вас ограничений нет. Rроме меня и группы Летичевского еще кто-то здесь из таких краев есть? Можно попробовать еще Лялецкого вытащить (http://ea.unicyb.kiev.ua/team...) Там, судя по рассказам такой островной эффект что аж вобще.P.S. Ссылки поправьте: http://www.cs.city.ac.uk/~let/...While trying to retrieve the URL: http://www.cs.city.ac.uk/~let/...The following error was encountered: Unable to determine IP address from host name for www.cs.city.ac.uk coi.city.ac.uk — работает

Ребята, NDA же все подписывали... читайте статьи — они в свободном доступе.+ Защищенные работы.В принципе можно понять основные направления развития.Штука очень хорошая. После знакомства по новому можно смотреть на многое.Я предполагаю, что развитие идет в интересах заказчика...А вообще — можно списаться и обсудить.

Да. APS не вспомнить нельзя:) (Но насколько я знаю, ничего в свободном доступе и доведенного до отдельного пакета нет) ВКстати, а сейчас он развивается? Есть кто из Мотороллы?

Тогда давайте уж упоминать и Летичевского с его идеями, что воплощались от МИРов до APS и APLAN’а.http://www.soi.city.ac.uk/~let/http://www.springerlink.com/co.../...+ то, что он сейчас делает

Re: А хотите язык, в котором вы сами будете определять и применять стратегии?) Так даже местное такое есть: http://www.gradsoft.ua/product...

Спасибо.Stratego — просто один из примеров. Действительно есть языки с встроенными возможностями.И для каждого класса задач возможно более подходит один нежели другой.

ili:

Не совсем в теме про LtU и AST — можно ссылку запостить?

LtU: Lambda the UltimateAST: Abstract Syntax Tree

//В предыдущем посте имелось в виду несколько функциональных языков...

ну да, насколько я понимаю Stratego настраивается на любой язык, с особой заточкой на их родной Tiger (диалект MetaML?). я вполне представляю себе, как это может быть использовано для расширения С++ или Java, чтобы добавить в язык что-то вроде JSP, LINQ, Pro*C или более ровного AspectJ., но зачем это языку, в котором подобные вещи есть изначально, как, например, в Scheme или в Template Haskell, я не совсем понимаю.

Не совсем в теме про LtU и AST — можно ссылку запостить? //В предыдущем посте имелось в виду несколько функциональных языков...

Некоторая терминологическая путаница возможна.Я имел в виду http://en.wikipedia.org/wiki/R... — техники переписывания и стратегии переписывания. В принципе переписыванием можно представить не только функциональные парадигмы, но и логические. Объектные вещи вроде тоже — сам не делал, но информация о возможности подобного есть.О C++ я ничего не писал. Есть много разных языков. Если сделать язык «контекстно свободным» (эх, понимать бы это на 100%:)) то можно получить много выгод.Давно подметил такую тенденцию: в проекте/продукте может быть использовано несколько языков. При этом новую функциональность пишут именно прототипами на ФЯ, а потом ради скорости перетаскивают вниз, на C++ уровень.Собственно иногда языков и более двух...И возможно к такому подходу приведет и развитие функциональности C#//Да, что-то слово ’функциональность’ функционально перегружено смыслами:)

ili:

А хотите язык, в котором вы сами будете определять и применять стратегии?)

...

http://www.stratego-language.o...

помнится Stratego обсуждали на LtU когда-то довольно активно. насколько я понял, это такой навороченный препроцессор для AST, настраиваемый на любой язык. для языков типа C++/Java это, может, и имеет смысл. однако, если AST доступен для изменений средствами родного языка, как в Scheme — есть ли смысл в еще какой-то сторонней системе, особенно если мы не хотим уходить слишком далеко от исходного синтаксиса? я не знаю.ну и насчет стратегий я не уверен — мне кажется, тут какая-то терминологическая путаница. в stratego, стратегия — это набор правил преобразования AST. таким образом, можно [теоретически] реализовать любую Evaluation strategy, но результат все равно будет комбинацией из strict и non-strict, не более того., а если учесть, что в stratego все это делается на базе заданного host language, то выбор и вовсе сокращается — ну вот попробуйте задать набор стратегий и сделать C++ ленивым языком? вот то-то же., а если уж создавать свой язык, так это вполне может быть и haskell, с его denotational semantics.

у ленивых вычислений очень короткое и простое определение.

поделись знанием? A scheduling policy under which no calculation is begun until it is certain that its result is needed. This policy contrasts with the eager evaluation used in most programs, but is often used in functional and logic programming.

f () and y () or z () — это не ленивые вычисления?

получается, что ленивые., но это частный случай (как мне кажется), которые присущ большинству языков, использующих eager evaluation.

askel:

Как можно напечатать то, чего еще нет (номер метки может быть известен не раньше, чем она была определена).

...

В пределе, ссылка в самом начале файла на метку, определенную в самом конце неминуемо приведет к необходимости задержки вывода до окончания ввода.

смотря как нумеровать ссылки. запросто можно сделать все за один проход по файлу, скажем, за O (n*log k) TIME и O (k) SPACE, где n это длина входных данных, а k — количество меток. если известен способ perfect hashing для меток, то можно и вовсе за O (n) справиться.

А как код на Haskell реагирует на больше, чем один пробельный символ? Я так понимаю, что в данном случае все, что между слов, съедается. А ошибки ввода как обрабатываются? А есть ли в Haskell механизм exceptions и “мелочи” типа try/catch?

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

Я вот точно знаю, что происходит внутри, а у Вас “_должен_ работать” — все на что Вы можете рассчитывать?

aw, shut up. я haskell не знаю, и сам статью читал с ручкой, бумажкой, и открытой сессией ghci на лаптопе. я — учусь, мне интересно, вот и вся “целесообразность”. буду знать больше — расскажу, а пока спасибо adept-y за то, что не ленится учить нас уму-разуму.Анонімно:

у ленивых вычислений очень короткое и простое определение.

поделись знанием? ili:

А хотите язык, в котором вы сами будете определять и применять стратегии?)

ты какой-то конкретный язык имеешь ввиду? ну расскажи.

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

смотря что понимать под ленивыми вычислениями..., а то так и оператор if это ленивые вычисления. по классике, различие между ленивыми и не ленывыми вычислениями (точнее, между strict и non-strict evaluation) — это то, что происходит с f () в вызове f (g ()).

у ленивых вычислений очень короткое и простое определение.

определяющим же фактором является то, какая именно стратегия принята в языке по умолчанию., а в таком случае все просто: Haskell и Clean — это ленивые языки, а lisp, python, ruby, scheme и прочие — нет.теперь понятно?

спасибо за небольшую лекцию, но это и так было понятно. непонятна фраза «Вот это уже совсем другое дело», но это я занудствую. спасибо автору за статью.

Хотелось бы увидеть реализацию этого алгоритма на Haskell с обработкой ошибок типа «метка определена больше одного раза», «пустая метка», «нет такой метки» с сохранением всех пробельных символов. Не наезда ради, а просто сравнить, насколько усложняется код, когда нужно писать что-то более-менее реальное, а не абстрактное.

но совсем не то, что происходит в хаскеле — там текст, в котором нет ссылок неразрешенных вперед, может быть напечатан тут же, не дожидаясь конца входного файла. (я не проверял, но он так _должен_ работать, это же ленивый пример): -)

Я вот точно знаю, что происходит внутри, а у Вас «_должен_ работать» — все на что Вы можете рассчитывать?

Вот и генераторы пригодились. Вариант, оптимизированный под случаи, когда ссылка не так далеко от метки. В идеале, между вводом и выводом только одна строка. Если нужно и такой вариант предусмотреть, когда все в одну строку, тоже не так уж и сложно.

class Ref: def init(self, label): self.label = labeldef parse(fd): import re patt = re.compile(r'([^@]*)(@(ref|label){([^}]*)})?', re.DOTALL | re.UNICODE) labels = {} deferred = [] for line in fd: for prefix, suffix, tag, label in patt.findall(line): if prefix: if not deferred: yield prefix else: deferred.append(prefix) if tag: label = label.strip() if not label: raise 'Empty label for "%s"' % tag if tag == 'label': if label in labels: raise 'Duplicate label "%s"' % label labels[label] = i = len(labels) + 1 deferred.append('[%s]' % i) elif tag == 'ref': deferred.append(Ref(label)) else: raise 'Unknown tag "%s"' % tag while deferred: top = deferred[0] if isinstance(top, basestring): yield top elif isinstance(top, Ref): if top.label not in labels: break yield 'see [%s]' % labels[top.label] deferred.pop(0)if name == 'main': import sys for chunk in parse(sys.stdin): sys.stdout.write(chunk)

А как код на Haskell реагирует на больше, чем один пробельный символ? Я так понимаю, что в данном случае все, что между слов, съедается. А ошибки ввода как обрабатываются? А есть ли в Haskell механизм exceptions и «мелочи» типа try/catch?

Хотя, если воспользоватся Deferred из twisted.internet.defer (практически, стандартная библиотека пайтона;)), то можно оптимизировать алгоритм для случаев, когда вывод готов раньше, чем мы прошлись по всему файлу, без особого напряга и усложнения алгоритма. Опять же, все зависит от пресловутой целесообразности;)

номер метки может быть известен не раньше, чем она была определена

В пределе, ссылка в самом начале файла на метку, определенную в самом конце неминуемо приведет к необходимости задержки вывода до окончания ввода.

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

Я, конечно, понимаю, что Haskell — «ленивый», но не до такой же степени;) Как можно напечатать то, чего еще нет (номер метки может быть известен не раньше, чем она была определена).

в любом случае, все в твоих руках, вне зависимости от языка., но питон — это не ленивый язык, по определению.

Случаи, когда «ленивые» вычисления нужны, достаточно редки. Посему, «ленивость по-умолчанию» видится сомнительным преимуществом.

да, будет (как минимум в ghc).

Уже неплохо

whatever. кому и кобол целесообразный язык.

Никто, кроме, пожалуй, фанатов, не начинает новые проекты на COBOL

Lisp is worth learning for the profound enlightenment experience you will have when you finally get it

Для меня этот этап был пройден лет пятнадцать назад. С тех пор я точно не подвяжусь сопровождать чужой код на Lisp. Писать на Lisp — легко и непринужденно. Можно сломать голову читая свой собственный код, написанный всего несколько лет назад;)

askel:

Для тех, кому лень разгребать неформатированный пайтоновский код, это реализация рассмотренного алгоритма с «ленивыми» вычислениями.

я вроде въехал в код — ты весь текст парсишь в память массив chunks. это близко, но совсем не то, что происходит в хаскеле — там текст, в котором нет ссылок неразрешенных вперед, может быть напечатан тут же, не дожидаясь конца входного файла. (я не проверял, но он так должен работать, это же ленивый пример): -)

А можно я сам буду определять, где мне нужны «ленивые» вычисления, а где нет?

в любом случае, все в твоих руках, вне зависимости от языка., но питон — это не ленивый язык, по определению.

К вопросу о юникоде в Haskell: приведенный выше пример на Haskell будет работать с юникодом?

да, будет (как минимум в ghc).

Я не знаю Haskell именно потому, что он все еще «экзотический язык» по причинам, упоминавшимся мною ранее, а не наоборот. Как только он перейдет из разряда таковых и появится целесообразнотсь в его изучении, буду учить.

whatever. кому и кобол целесообразный язык.Lisp is worth learning for the profound enlightenment experience you will have when you finally get it; that experience will make you a better programmer for the rest of your days, even if you never actually use Lisp itself a lot. — Eric S. Raymondтак-то.

тут симптоматично уже то, что все незнакомые технологии валятся в одну кучу «экзотических языков»

Давайте не будем нарушать причинно-следственные связи и пытаться устанавливать друг-другу диагноз:) Я не знаю Haskell именно потому, что он все еще «экзотический язык» по причинам, упоминавшимся мною ранее, а не наоборот. Как только он перейдет из разряда таковых и появится целесообразнотсь в его изучении, буду учить. И дело вовсе не в популярности. Меня, к примеру, ничем не прельщают популярные нынче «рельсы», поскольку вполне устраивает Python. И я точно не хотел бы возвращаться к Perl или Java, хотя знаю (знал в свое время?) эти языки достаточно хорошо.

Эх, спамить, так спамить!:) По-хорошему, нужно так

patt = re.compile(r'(.*)(@(ref|label){([^}]*)})?', re.DOTALL)...for prefix, rest, tag, label in patt.findall(line): # скрипач не нужен

определяющим же фактором является то, какая именно стратегия принята в языке по умолчанию., а в таком случае все просто: Haskell и Clean — это ленивые языки, а lisp, python, ruby, scheme и прочие — нет.

А можно я сам буду определять, где мне нужны «ленивые» вычисления, а где нет? К вопросу о юникоде в Haskell: приведенный выше пример на Haskell будет работать с юникодом?

Для тех, кому лень разгребать неформатированный пайтоновский код, это реализация рассмотренного алгоритма с «ленивыми» вычислениями.Это дело работает начиная с версии 2.1, т.е. пайтон поддерживает closures около шести лет.

Господи, да что же это такое. Опять то же самое: (

Хм, что-то с форматированием случилось. Простите, что намусорил. Попробую еще разок. Не бейте, если опять не выйдет, так как предварительного просмотра нет: (

def ref(labels, label): class LazyRef: def str(self): return 'see [%s]' % labels[label] return LazyRef()def parse(fd): import re patt = re.compile(r'([^@]*)(@(ref|label){([^}]*)}([^@]*))?') chunks = [] labels = {} for line in fd: for prefix, rest, tag, label, suffix in patt.findall(line): if prefix: chunks.append(prefix) if rest: if tag: label = label.strip() if not label: raise 'Empty label for "%s"' % tag if tag == 'label': if label in labels: raise 'Duplicate label "%s"' % label labels[label] = i = len(labels) + 1 chunks.append('[%s]' % i) elif tag == 'ref': chunks.append(ref(labels, label)) if suffix: chunks.append(suffix) return chunksif name == 'main': import sys for chunk in parse(sys.stdin): print chunk,

def ref(labels, label): class LazyRef: def str(self): return 'see [%s]' % labels[label] return LazyRef()def parse(fd): import re patt = re.compile(r'([^@]*)(@(ref|label){([^}]*)}([^@]*))?') chunks = [] labels = {} for line in fd: for prefix, rest, tag, label, suffix in patt.findall(line): if prefix: chunks.append(prefix) if rest: if tag: label = label.strip() if not label: raise 'Empty label for "%s"' % tag if tag == 'label': if label in labels: raise 'Duplicate label "%s"' % label labels[label] = i = len(labels) + 1 chunks.append('[%s]' % i) elif tag == 'ref': chunks.append(ref(labels, label)) if suffix: chunks.append(suffix) return chunksif name == 'main': import sys for chunk in parse(sys.stdin): print chunk,
тьфу, повесил переключение на русский на caps lock, и теперь все время попадаю на сочетание tab+space... вы уж извините за неровный почерк: -)

говорить о том, что «питон роддерживает ленивые вычисления при помощи генераторов», по-моему вообще не корректно., а если бы в питоне небыло генераторов, он перестал бы поддерживать ленивые вычисления? f () and y () or z () — это не ленивые вычисления?

смотря что понимать под ленивыми вычислениями..., а то так и оператор if это ленивые вычисления. по классике, различие между ленивыми и не ленывыми вычислениями (точнее, между strict и non-strict evaluation) — это то, что происходит с f () в вызове f (g ()). если g () = |, т.е., скажем, бесконечный цикл или эксепшн, то в не-ленивом языке f () гарантированно не вызовется.понятно, что все это можно обойти — скажем, завернуть вызов g () в функциональный объект, как в С++, или использовать макро, как в лиспе, или сделать что-то вроде delay/force в Scheme. аналогично, в non-strict языке есть способы принудительно вычислить то или иное выражение.определяющим же фактором является то, какая именно стратегия принята в языке по умолчанию., а в таком случае все просто: Haskell и Clean — это ленивые языки, а lisp, python, ruby, scheme и прочие — нет.теперь понятно?

говорить о том, что «питон роддерживает ленивые вычисления при помощи генераторов», по-моему вообще не корректно., а если бы в питоне небыло генераторов, он перестал бы поддерживать ленивые вычисления? f () and y () or z () — это не ленивые вычисления?

смотря что понимать под ленивыми вычислениями..., а то так и оператор if это ленивые вычисления. по классике, различие между ленивыми и не ленывыми вычислениями (точнее, между strict и eager evaluation) — это то, что происходит с g () в вызове f (g ()). если g () = _|_, т.е., скажем, бесконечны

про то же отсутствие юникода в хаскеле (я так понимаю из контекста, что именно он имелся ввиду?) — сам придумал или рабинович напел? и каких именно библиотек вам не хватает?

То, что в Haskell имеется некая библиотека (-ки) для работы с юникодом, погоды не делает. Все остальные библиотеки должны использовать эту возможность, иначе толку мало.

велика вероятность того, что хороший программист сам к вам прийдет только ради Haskell-a или OCaml-a. еще один вариант — самому стать хорошим программером на Haskell-e, но вы такой вариант не рассматриваете, как я понимаю.

Вероятность того, что я вообще не найду хорошего программиста гораздо больше и я бы не рискнул поставить серьезный проект в зависимость от удачи. Даже если я стану экспертом в Haskell, это не намного улучшит ситуацию — я могу «свалить», помереть, и пр. Да и для серьезного проекта одного человека не всегда достаточно.

К тому же, питон поддерживает ленивые вычисления при помощи генераторов, и в нем возможно Partial Function Application.

насколько я могу судить, то, что описано в functools под именем partial — это замыкание, потому что результат partial с меньшим чем надо числом параметров не возвращает новую функцию, а выдаёт ошибку. получить новую функцию можно с помощью ещё одного partial, т.е. ещё раз сделав замыкание. ака сделав тоже самое, что описывалось выше.говорить о том, что «питон роддерживает ленивые вычисления при помощи генераторов», по-моему вообще не корректно., а если бы в питоне небыло генераторов, он перестал бы поддерживать ленивые вычисления? f () and y () or z () — это не ленивые вычисления?

сорри, не ту кнопку нажал.askel:

Все это, конечно, очень интересно, но не более того.

ИМНО одно то, что это интересно, уже стоит времени и усилий, потраченных на изучение.

Практическая ценность подобных экзотических зяыков сводится к нулю отсутствием поддержки юникода, отсутствием готовых и отлаженных библиотек, и прочих «мелочей», без которых все это так и останется игрушкой.

тут симптоматично уже то, что все незнакомые технологии валятся в одну кучу «экзотических языков». что там Paul Graham говорил про Blub? ну и остальное тоже полная лажа. про то же отсутствие юникода в хаскеле (я так понимаю из контекста, что именно он имелся ввиду?) — сам придумал или рабинович напел? и каких именно библиотек вам не хватает? а вооще, скажу по секрету, практически в любом новом языке вначале нет ни библиотек, ни готовых фреймворков, ни «мелочей». как вообще DHH за руби взялся — ни библиотек, ни юникода (кстати), ни программистов со знанием языка?

Да и, в конце концов, где я буду искать хорошего программера на Haskell для сопровождения имеющегося кода? Именно сопровождение, а не просто «написал и забыл», требует хороших программеров. Написать и забыть могут и студенты.

велика вероятность того, что хороший программист сам к вам прийдет только ради Haskell-a или OCaml-a. еще один вариант — самому стать хорошим программером на Haskell-e, но вы такой вариант не рассматриваете, как я понимаю.

askel:

Все это, конечно, очень интересно, но не более того.

одно то, что это интересно, уже стоит времени и усилий Практическая ценность подобных экзотических зяыков сводится к нулю отсутствием поддержки юникода, отсутствием готовых и отлаженных библиотек, и прочих «мелочей», без которых все это так и останется игрушкой. Да и, в конце концов, где я буду искать хорошего программера на Haskell для сопровождения имеющегося кода? Именно сопровождение, а не просто «написал и забыл», требует хороших программеров. Написать и забыть могут и студенты.

interesno, pishite esche %) a to ruki do knijki po Haskell nikak ne doydut (

Да, есть желание не согласиться с askel, но приведенные аргументы вполне согласуются с практикой...Но: если за это можно получить хорошие деньги то такие «мелочи» могут решаться.

Все это, конечно, очень интересно, но не более того. Практическая ценность подобных экзотических зяыков сводится к нулю отсутствием поддержки юникода, отсутствием готовых и отлаженных библиотек, и прочих «мелочей», без которых все это так и останется игрушкой. Да и, в конце концов, где я буду искать хорошего программера на Haskell для сопровождения имеющегося кода? Именно сопровождение, а не просто «написал и забыл», требует хороших программеров. Написать и забыть могут и студенты.

Боже, как сложно!:) У меня в подобных случаях всегда возникал вопрос... №%х%я?:) Я понимаю, что это наглядный пример (пропарсить текст, вставить ссылки).Но, блин, в каких РЕАЛЬНЫХ случаях рядовой программист (под Web, насколько я понимаю сферу применения) должен строить ТАКИЕ абстрактные построения, что бы получить от них результат? Не усложняете ли вы себе жизнь, уважаемые?:) P.S. Ответ «Да ты нихрена в этом не смыслишь! » — принимается:)

сорри ребята, что-то я туплю: -)

splitToWords = unzip . (uncurry zip =<<) . zip (map repeat [1..]) . map words . lines

haskell overdose

да чтоб его! =&& =

aargh! let’s see if this one will get through:

splitToWords = unzip . (uncurry zip =&&) . zip (map repeat [1..]) . map words . lines

ADEpt: ай как здорово! молодчина, что написал. читаю с огромным удовольствием, и жду продолжения:) PS. a pointless remark:

splitToWords = unzip . (uncurry zip =(pun intended) :-)до чего все-таки красивый язык.

Питон в этом списке лишний: в нем (в отличии от c++ и java) функции как раз first class objects. К тому же, питон поддерживает ленивые вычисления при помощи генераторов, и в нем возможно Partial Function Application.

О. Вот это уже совсем другое дело:) Синтаксис монстроватый на мой вкус, но вкус — это дело такое... Вычеркиваем.

насчёт функции g не понятно. и там, и там список списков, почему вложенность списка должна повлиять на выборку...

А вы посчитайте внимательно уровень вложенности. Возможно со строками будет понятнее (насколько я помню, в python со строками тоже можно работать как со списком символов):

Prelude> let g = map (!!1)Prelude> g ["ab","cd","ef"]"bdf"Prelude> map g [ ["ab","cd","ef"], ["gh","ij","kl"] ]["bdf","hjl"]

...если функции передать больше 3 параметров, то она становится бесполезной, но ещё одна проверка кол-ва параметров может это исправить.

Ну, как я и писал, приходится писать код, учитывающий особенности каждой конкретной пары функций. Увы: (

насчёт функции g не понятно. и там, и там список списков, почему вложенность списка должна повлиять на выборку...а насчёт композиции, то пример выше — это замыкание. поэтому, если я правильно понимаю, нужно что-то вроде замыкания замыкания. наверное как-то так:

def add3(*args):def inner_add(*fargs):tmpargs = self.inner_args + fargsif len(tmpargs) == 3: return tmpargs[0] + tmpargs[1] + tmpargs[2]else: return add3(*tmpargs)self = inner_addself.inner_args = argsreturn self

f1 = add3 (1, 2) f1 (3) == 6f2 = add3 (1, 7, 10) f2 () == 18f3 = add3 (4) f3 (6, 7) == 17f4 = add3 (6) f5 = f4 (10) f5 (8) == 24если функции передать больше 3 параметров, то она становится бесполезной, но ещё одна проверка кол-ва параметров может это исправить.

может быть питон зря включён в список языков или задание сформулировано неверно?

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

map

и операции взятия первого эл-та списка соорудить такую функцию

g

, что:

g [[1,2],[3,4],[5,6]] вернет [2,4,6]map g [[[1,2],[3,4],[5,6]],[[1,2],[3,4],[5,6]]] вернет [[2,4,6],[2,4,6]]

Я подозреваю, что к приведеному примеру понадобится добавить еще один враппер с «return innerf», так? Если да, то получается, что функции в python — они как бы first-class, но радости от этого не очень много. Почему не очень много? Потому, что способов создания новых функций — не очень много (как я помню, только с помощью лямбд и можно), в частности — каррирования (частичного применения) нет. Вместо «map (! 1) » надо написать две функции-враппера, и так — для каждого частичного применения. Кстати, а можно ли написать универсальную функцию, реализующую композицию функций (не обязательно с одним аргументом, так что тоже требуется частичное применение)?

пардон, вот видимо то, что имелось ввиду. вопрос тот же.>>> def f (i): ... def innerf (l): return l [i] ... return innerf... >>> def mmap (f, l): return [f (x) for x in l] ... >>> l = [[1, 2], [3, 4], [5, 6]] >>> mmap (f (1), l) [2, 4, 6] >>> mmap (f (0), l) [1, 3, 5]

можете попробовать определить на C++/Python/Java аналоги функций map и!

может быть питон зря включён в список языков или задание сформулировано неверно?

В качестве упражнения номер два можете попробовать определить на C++/Python/Java аналоги функций map и! так, чтобы их можно было комбинировать в стиле map (! 1) и самостоятельно сделать вывод о том, являются ли функции полноправными сущностями в этих языках.

вроде обычный делегат.>>> def mmap (f, l): return [f (x) for x in l] ... >>> mmap (lambda l: l [1], [[1, 2], [3, 4], [5, 6]]) [2, 4, 6] так какой вывод?

В цьому абзаці треба поправити лінки.

Дякую, виправлено.

Особо обратите внимание на последний пример: используя информацию о том, что (!) возвращает элемент списка, компилятор самостоятельно вычислил, что выражение-функция map (! 1) будет преобразовывать список списков в список просто значений. Самостоятельно посмотрите на тип функций map, (!) и (! 1), чтобы понять, как именно компилятор произвел вывод. Подобный алгоритм выведения типов используется также в языках Clean, ML, OCaml, Scala, Nemerle, D. Ожидается, что вывод типов появится в C# 3.0 и Perl 6 (помните, что я говорил о влиянии ФП на mainstream языки?).

В цьому абзаці треба поправити лінки.

Подписаться на комментарии