Когода кто-то пишет статьи о фунциональном программировании, то почему-то в качестве примеров всегда используются вещи вроде фунций Фибоначи и тому подобной бесполезной фигни.
Это приводит к тому, что у людей закрадывается сомнение, что данные возможности полезны в области математики, парсинга или еще какой-то специализированной области оторванной от жизни.
Предлагаю совместными усилиями подобрать набор примеров которые с одной стороны не требовали бы вникания в некоторую сложную задачу с другой демонстрировали приемущества функциональных языков (first class-функций, алгеброических типов, сопоставления с образцом).
Приветсвуются любые примеры.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: Требуются примеры использования first class function и p
Здравствуйте, VladD2, Вы писали:
VD>Когода кто-то пишет статьи о фунциональном программировании, то почему-то в качестве примеров всегда используются вещи вроде фунций Фибоначи и тому подобной бесполезной фигни.
VD>Это приводит к тому, что у людей закрадывается сомнение, что данные возможности полезны в области математики, парсинга или еще какой-то специализированной области оторванной от жизни.
VD>Предлагаю совместными усилиями подобрать набор примеров которые с одной стороны не требовали бы вникания в некоторую сложную задачу с другой демонстрировали приемущества функциональных языков (first class-функций, алгеброических типов, сопоставления с образцом).
VD>Приветсвуются любые примеры.
За! Правда, сам с ходу ничего предложить не могу, т.к. только учусь... Однако, хотелось, чтобы задачи были реализованы на ИЯ(С++, С#, Java, Python, Ruby), ФЯ (List, ML, Haskel, Erlang) и гибридных (Величайший Язык Современности, Scala, OCaml).. Думаю, достаточно бросить клич, и любители языков засыплют реализациями.. А потом все это склеить — и получим side-by-side сравнение, причем достаточно полезное, так как новичкам (таким, как я), легче будет увидеть, где лучше использовать функциональный подход, а где — императивный.
Re: Требуются примеры использования first class function и p
let rseed = ref 1234;;
let random () =
let nrs = (!rseed) * 214013 + 2531011 in
rseed := nrs;
(nrs lsr 16) land 0x7FFFFFFF;;
let rec lcreate func lst = function
0 -> lst
| n -> lcreate func ((func n)::lst) (n-1);;
let applay_mods mods h n =
let (x,y) = (n mod h, n / h) in
let ffun el f = f el x y in
List.fold_left ffun (0,0,0,0) mods;;
let create_modifier w h _ =
let x1 = (random ()) mod w
and y1 = (random ()) mod h
and x2 = (random ()) mod w
and y2 = (random ()) mod h
and cr = (random ()) mod 255
and cg = (random ()) mod 255
and cb = (random ()) mod 255
and ca = (random ()) mod 255 in
let (nx1,nx2) = if (x1 > x2) then (x2, x1-x2+1) else (x1, x2-x1+1)
and (ny1,ny2) = if (y1 > y2) then (y2, y1-y2+1) else (y1, y2-y1+1) in
fun ((r,g,b,a) as point) x y ->
if ((x < nx1) || (x > nx2) || (y < ny1) || (y > ny2)) then point else
let nr = ((((cr-r)*ca) lsr 8) + r) land 255
and ng = ((((cg-g)*ca) lsr 8) + g) land 255
and nb = ((((cb-b)*ca) lsr 8) + b) land 255
and na = (ca*a-((ca*a) lsr 8)) land 255 in
(nr, ng, nb, na);;
let test_alpha_blend w h n =
let mods = lcreate (create_modifier w h) [] n in
lcreate (applay_mods mods h) [] (w*h);;
let main () =
let w = 1000
and h = 1000
and n = 1000 in
test_alpha_blend w h n;;
main ();;
Re: Требуются примеры использования first class function и p
Здравствуйте, Mamut, Вы писали:
VD>>Приветсвуются любые примеры.
M>Для затравки quicksort и insertion sort на Эрланге сгодятся?
Сгодится. Но примеры не к черту. Кому нужны супер тормозные реализации алгоритмов давно в оптимальном виде имеющиеся влюбой библиотеке?
Нужны просые примеры для демонстрации сути подхода. Лучше чето-нить из того что многие используют на прктике. Ну, там работа с данными, ГУИ (возможно) или еще что-то.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: Требуются примеры использования first class function
Я наверно не плохо изложил свою мысль. Ни в коем случае не нужны сложные алгоритмы. К тмоу же средний программист применяет альфа блэндинг еще резе чем Фибоначи.
Я сам в ступоре. Не раз испоьзовал те же FCF на практике, но как-то все это частные решения и как пример они лохо подходят.
А есть ли какие-нибудь совсем простые примеры (туториалы, что ли)? Может там поискать?
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: Требуются примеры использования first class function и p
так ты вопрос задал, навроде "приведите примеры использования циклов и полиморфизма"...
конечно сразу не догадаешься что тут вместо коллекций и фигур на экране в пример приводить...
тут наверно, как в императивщине — смотришь в чужой код, иногда думаешь, о! интересный оборот...
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re: Требуются примеры использования first class function и p
Конечно, хотелось бы универсальный пример, показывающий что:
1. Функции могут присвоены переменным.
2. Функции могут быть переданы как параметры.
3. Функции могут быть возвращены как значения.
4. Функции могут учавствовать в определении структур данных.
Пример охватывающий сразу три первых пункта: символьное дифференцирование — на вход подаётся функция, на выходе тоже функция.
Тривиальный пример на четвёртый пункт — реализация хэш-таблицы. Мне не нравится он тем, что функция-параметр статическая (после определения не меняется) — не видно преимуществ по сравнению с указателями.
Более сложный пример подразумевает хранение в качестве ключа "символ", а в качестве значения какой-нибудь функции для последующей диспетчеризации, скажем реализации интерпретатора. Ничего не стоит реализовать определение новых операций с возможностью непосредственного исполнения.
Здравствуйте, VladD2, Вы писали:
VD>Ну, там работа с данными, ГУИ (возможно) или еще что-то.
Для ГУИ здорово подходят макросы Nemerle, пока дизайнера форм нет, и частичное применение. Вот про макросы (из реального проекта):
CreateNameValueDialog(150, this,
{
| "Number of inputs" => udInputs : NumericUpDown ( Maximum = 8, Value = 1)
| "Number of outputs" => udOutputs : NumericUpDown ( Minimum = 1, Maximum = 8, Value = 1)
})
Что делает, мне кажется, примерно ясно. Заодно может задекларировать поля в классе, если их нет.
Только использовать подобные фишки в качестве примеров не стоит наверно... А для FCF хороший пример — какой-нить парсер, или лучше преобразователь деревьев.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[2]: Требуются примеры использования first class function
LCR>Конечно, хотелось бы универсальный пример, показывающий что: LCR>1. Функции могут присвоены переменным. LCR>2. Функции могут быть переданы как параметры. LCR>3. Функции могут быть возвращены как значения. LCR>4. Функции могут учавствовать в определении структур данных.
LCR>Пример охватывающий сразу три первых пункта: символьное дифференцирование — на вход подаётся функция, на выходе тоже функция.
вот здесь я не понял, то есть совсем не понял... (потому что математическая функция и программная функция, это 2 большие разницы)
можно чуть подробней, т.к. мне это очень интересно
LCR>Тривиальный пример на четвёртый пункт — реализация хэш-таблицы. Мне не нравится он тем, что функция-параметр статическая (после определения не меняется) — не видно преимуществ по сравнению с указателями.
LCR>Более сложный пример подразумевает хранение в качестве ключа "символ", а в качестве значения какой-нибудь функции для последующей диспетчеризации, скажем реализации интерпретатора. Ничего не стоит реализовать определение новых операций с возможностью непосредственного исполнения.
тут тоже не понял (в т.ч. что это за "символ"), но это в принципе, менее важно
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[2]: Требуются примеры использования first class function
Здравствуйте, Андрей Хропов, Вы писали:
АХ>Здравствуйте, VladD2, Вы писали:
АХ>Тут есть кое-что.
АХ>Хороший пример паттерн-матчинга — парсинг XML (да и текста тоже): АХ>Собственно в туториалах к Немерле есть.
Вот аналогичный(?) пример на Scala
и вообще вот эта страница.
--
WBR, Alexander
Re: Требуются примеры использования first class function и p
Очень поддерживаю инициативу. Весьма интересная проблема.
VD>Это приводит к тому, что у людей закрадывается сомнение, что данные возможности полезны в области математики, парсинга или еще какой-то специализированной области оторванной от жизни.
А может быть так оно и есть?
VD>Предлагаю совместными усилиями подобрать набор примеров которые с одной стороны не требовали бы вникания в некоторую сложную задачу с другой демонстрировали приемущества функциональных языков (first class-функций, алгеброических типов, сопоставления с образцом).
Мне понравился пример паттерн матчинга в Yet Another Haskell Tutorial. Раздел 7.4. Там и алгебраические типы есть, и задача не слишком оторванная от жизни (цвета в виде названий и в форме RGB). Да и вообще в этом тьюториале довольно много неплохих примеров, имхо.
VD>Приветсвуются любые примеры.
В какой форме готовить будем?
PS. Может быть у меня опыта маловато в ФП, но всеже красота функционального решения, имхо, особенно хорошо чувствуется именно в нетривиальных задачах.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re: Требуются примеры использования first class function и p
Здравствуйте, VladD2, Вы писали:
VD>Предлагаю совместными усилиями подобрать набор примеров которые с одной стороны не требовали бы вникания в некоторую сложную задачу с другой демонстрировали приемущества функциональных языков (first class-функций, алгеброических типов, сопоставления с образцом).
VD>Приветсвуются любые примеры.
PhantomIvan,
LCR>>Пример охватывающий сразу три первых пункта: символьное дифференцирование — на вход подаётся функция, на выходе тоже функция.
PI>вот здесь я не понял, то есть совсем не понял... (потому что математическая функция и программная функция, это 2 большие разницы) PI>можно чуть подробней, т.к. мне это очень интересно
Да, совершенно верно (про выделенное). На этом примере хорошо видна разница между указателями на функции и ФВП. А также разница между Лиспом и не-Лиспом.
Итак, предположим, у нас есть некоторый вычислительный алгоритм, которому требуется для работы как сама функция f, так и её производная df (ну например, метод Ньютона, или скажем мы делаем свой собственный Maple ).
У нас есть путь классический — каждый раз когда нам понадобится запустить алгоритм для новой функции f, мы определяем новое тело для функции f и новое тело для функции df. Перекомпилируем. Запускаем... В случае Java/C# у нас есть костыли типа эмиттеров-загрузчиков.
В качестве альтернативы мы можем написать класс-интерпретатор, обёртку над AST, и операция дифференцирования будет расковыривать AST и генерировать новое T. У этого решения есть недостатки, в частности тот, что внешняя функция должна лезть в кишки интерпретатора. Придётся создавать абстрактный слой доступа к AST и т.п. Ну и этот велосипед конечно же будет подчиняться 10-му закону Гринспуна.
Вот путь Лиспа. Нам нужно просто написать функции типа (number? ...), (variable? ...).
(deriv '(* (* x y) (+ x 3)) 'x)
(+ (* (* x y) (+ 1 0))
(* (+ (* x 0) (* 1 y))
(+ x 3)))
То, что выдала функция deriv — это полноценная функция. Её можно например передать в функцию рисования графиков, и будет нарисован график. Если полученное выражение кажется многословным, можно утоптать до минимального вида совершенно аналогичной функцией simplify. (В примере ниже будет одна из реализаций этой функции).
Вот путь Хаскеля. Поскольку в данном случае у нас уже нет волшебного порошка code is data is code , то придётся использовать алгебраические типы. Но с другой стороны это и преимущество, потому что уже работает паттерн-матчинг вместо (cond ...). Выглядеть это будет примерно так:
-- строительные блоки для выраженийinfixl 5 :+
infixl 6 :*
data Exp = Num Integer
| Var Sym
| Exp :+ Exp
| Exp :* Exp deriving (Eq,Show)
data Sym = X | Y deriving (Eq,Show)
main = do let exp = (Num 4 :* Var X :* Var X)
let deriv = d exp X
putStrLn $ "Original expression : " ++ (show exp)
putStrLn $ "Derivative : " ++ (show $ simplify deriv)
putStrLn $ "Derivative evaluated at X=10 : "
++ (show $ eval (d exp X) [(X,10)])
-- взять производную
d (Num n) x = Num 0
d (Var y) x | x==y = Num 1
| otherwise = Num 0
d (f :+ g) x = (d f x) :+ (d g x)
d (f :* g) x = (d f x) :* g :+ f :* (d g x)
-- вычислить выражение типа Exp...
eval (Num x) env = x
eval (Var x) env = case (lookup x env) of
(Just n) -> n
(Nothing) -> error $ "no variable "++(show x)++" in env"
eval (x :+ y) env = eval x env + eval y env
eval (x :* y) env = eval x env * eval y env
-- несколько алгебраических правил для упрощения
simp (x :+ y) | x == y = simp (Num 2):*x
simp ((Num 0) :+ x) = simp x
simp (x :+ (Num 0)) = simp x
simp ((Num x) :+ (Num y)) = Num (x+y)
simp (x :+ y) = simp x :+ simp y
simp ((Num 0) :* x) = Num 0
simp (x :* (Num 0)) = Num 0
simp ((Num 1) :* x) = simp x
simp (x :* (Num 1)) = simp x
simp ((Num x) :* (Num y)) = Num (x*y)
simp (x :* y) = simp x :* simp y
simp x = x
-- применять правила упрощения до тех пор, пока выражение не перестанет меняться
simplify x = let a = iterate simp x
fix = dropWhile (\(c,d)->c/=d) $ zip a (tail a)
in (fst.head) fix
Вышеприведённый код выведет примерно следующее:
Original expression : (Num 4 :* Var X) :* Var X
Derivative : Num 2 :* (Num 4 :* Var X)
Derivative evaluated at X=10 : 80
Владу скорее всего пример не понравится, потому что слишком заумный и оторванный от жизни. А мне очень нравится, более того, могу сказать, что современные оптимизаторы в компиляторах — это функции типа simp, только естественно гораздо более сложные.
LCR>>>Пример охватывающий сразу три первых пункта: символьное дифференцирование — на вход подаётся функция, на выходе тоже функция.
PI>>вот здесь я не понял, то есть совсем не понял... (потому что математическая функция и программная функция, это 2 большие разницы) PI>>можно чуть подробней, т.к. мне это очень интересно
LCR>В качестве альтернативы мы можем написать класс-интерпретатор, обёртку над AST, и операция дифференцирования будет расковыривать AST и генерировать новое T. У этого решения есть недостатки, в частности тот, что внешняя функция должна лезть в кишки интерпретатора. Придётся создавать абстрактный слой доступа к AST и т.п. Ну и этот велосипед конечно же будет подчиняться 10-му закону Гринспуна.
вот, я как-нибудь подобное реализую, а что такое 10 закон Гринспуна? что все сложное ломается?
LCR>Вот путь Лиспа.
вот эта вот концепция: code is data is code очень даже подходит для символьных вычислений
но я как статически типизированный мэн, должен спросить: насколько реально это перетянуть к себе?
(как насчет: вычисляем в рантайм -> кидаем обратно в сорс?)
LCR>Вот путь Хаскеля.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Если нам не помогут, то мы тоже никого не пощадим.
