VPF::Imperative v. Functional - Форум программистов

Cr@$h

Дата 28.2.2006, 20:02 (ссылка)

(нет голосов)

Загрузка ...

Исследователь

Профиль
Группа: Участник Клуба
Сообщений: 1693
Регистрация: 3.4.2005
Где: Санкт-Петербург, Россия

Репутация: нет
Всего: 41

Википедия все правильно написала по этому поводу и с Void я согласен. В третьих шарпах ведб тоже вводят, наконец, функциональные средства.
Например, Пролог так считается языком логического программирования, а там есть и императивность, и функциональность, и ООП и многое другое.

ДобренькийПапаша

Дата 28.2.2006, 21:05 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1278
Регистрация: 14.1.2006
Где: г.Москва

Репутация: нет
Всего: 7

А правда то, что 90% прог написаны на С++?

--------------------

Меня зовут Себастьян Парейра, торговец чёрным деревом.

Cr@$h

Дата 28.2.2006, 21:12 (ссылка)

(нет голосов)

Загрузка ...

Исследователь

Конечно, нет. Спасибо за флуд темы.

setq

Дата 2.3.2006, 17:03 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Выкладываю реализацию словарей на базе AVL деревьев на языке Hope.

Цитата(Wikipedia)

Hope is a small functional programming language, with strong polymorphic typing, algebraic data types, pattern matching, and higher-order functions. It has call-by-pattern evaluation. The first implementation of Hope was strict, but since that one there have been lazy versions and strict versions with lazy constructors. Hope is purely functional.

На языке написаны примеры к книге "Функциональное программирование" Филда & Харрисона, так что я его немного знаю.

Подкупило слово small smile

Модуль с функциями для списков:

Код


! list.hop
! list related functions



typevar a ;

dec break : list(a) # num -> list(a) # list(a) ;
! break([x1,...xn], i) <= [x1,...xi], [x(i+1),...xn]
--- break(P, 0) <= [], P ;
--- break(p::P, succ(n)) <=
  p::Q, R where
    Q, R == break(P, n) ;


dec break2 : list(a) -> list(a) # list(a) ;
--- break2(P) <= break(P, length(P)/2) ;


! there must be a standard implementation
! of sort()... anyway

dec merge : list(a) # list(a) -> list(a) ;
--- merge([], Q) <= Q ;
--- merge(P, []) <= P ;
--- merge(p::P, q::Q) <=
  if p=<q then p::merge(P, q::Q) else
  q::merge(p::P, Q) ;


dec sort : list(a) -> list(a) ;
--- sort([]) <= [] ;
--- sort(P) <=
  let Q, R == break2(P) in
    merge(sort(Q), sort(R)) ;

"Деревья":

Код


! tree.hop
! tree and AVL tree data types

use list ;



typevar a ;


data tree(a) == Tip ++ Node(tree(a) # a # tree(a)) ;


dec find_node : tree(a) # a -> tree(a) ;
--- find_node(Tip, _) <= Tip ;
--- find_node(T, p) <=
  let Node(lt, p', rt) == T in
    if p<p' then find_node(lt, p) else
    if p=p' then T else
    find_node(rt, p) ;  ! if p>p'


dec flatten : tree(a) -> list(a) ;
--- flatten(Tip) <= [] ;
--- flatten(Node(l, p, r)) <= flatten(l) <> [p] <> flatten(r) ;



type avl(a) == tree(a) ;


dec toAvl : list(a) -> avl(a) ;
dec _toAvl : list(a) -> avl(a) ;

--- _toAvl([]) <= Tip ;
--- _toAvl(P) <=
  let Q, r::R == break2(P) in
    Node(_toAvl(Q), r, _toAvl(R)) ;
--- toAvl(P) <= _toAvl(sort(P)) ;

Модуль с типом Association (Как в Smalltalk'е. Почти.)

Код


! association.hop
! association data type (Blank -- is kind of
! empty constructor for comparison purposes)



typevar a, b ;


infix ## : 9 ;
data assoc(a, b) == Blank(a)  ++  a ## b ;


! association is compaired by keys
--- compare(Blank(p), Blank(q)) <= compare(p, q) ;
--- compare(Blank(p), q ## _) <= compare(p, q) ;
--- compare(p ## _, Blank(q)) <= compare(p, q) ;
--- compare(p ## _, q ## _) <= compare(p, q) ;

Собственно, модуль с определением словаря:

Код


! dictionary.hop
! dictionary data type

use association, tree ;



typevar a, b ;

type dict(a, b) == avl(assoc(a, b)) ;


dec add : dict(a, b) # a # b -> dict(a, b) ;
--- add(D, k, v) <= toAvl(k##v :: flatten(D)) ;


dec has : dict(a, b) # a -> bool ;
--- has(D, k) <= find_node(D, Blank(k)) = Tip ;


dec del : dict(a, b) # a -> dict(a, b) ;
--- del(D, k) <= toAvl(filter(flatten(D), lambda x => x=Blank(k))) ;


dec get : dict(a, b) # a -> b ;
--- get(D, k) <=  v where Node(_, _ ## v, _) == find_node(D, k) ;


dec toDict : list(a # b) -> dict(a, b) ;
--- toDict(P) <= toAvl(map(P, lambda(x, y) => x ## y)) ;

С сессией пользователя у меня проблемы — не помню я как shell у hop'а выглядит, а UNIX'а под рукой нету. Так что даю только начальные предложения:

Код


use dictionary ;

! let's extend standard function compare()
! to compare strings (because i'm not sure
! wether Hope can do it)

--- compare([], []) <= EQUAL ;
--- compare(p::P, []) <= GREATER ;
--- compare([], q::Q) <= LESS ;
--- compare(p::P, q::Q) <=
  if p>q then GREATER else
  if p=q then compare(P, Q) else
  LESS ;  ! if p<q


: myList <= [("Beatles", "Because"),
             ("Distillers", "Black Heart"),
             ("My Bloody Valentine", "Soon"),
             ("Portishead", "Roads"),
             ("Blonde Redhead", "Falling Man")] ;

: myDict <= toDict(map(myList, lambda(x, y) => (y, x))) ;

: get(myDict, "Black Heart") ;
"Distillers" : list(char)

Наверно так.
Повторюсь, не прогонял, не тестировал. Готов в принципе по первому требованию установить себе FreeBSD и отладить...

Интересно... Сколько всё-таки % прог написано на C++? smile

Это сообщение отредактировал(а) setq - 3.3.2006, 21:43

Void

Дата 2.3.2006, 21:17 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

setq, увидев столь краткий код, я основательно перепугался и подумал, что пропустил в Hope что-то очень интересное. Но, оказывается, ты реализовал обычные бинарные деревья. Или я все-таки потерял где-то в этих 84 строчках балансировку? smile

Цитата(setq @ 2.3.2006, 19:03

)

Сколько всё-таки % прог написано на C++?

С точки зрения дзен, гораздо интереснее вопрос: сколько еще ненаписанных программ не будет написано на C++? smile

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

setq

Дата 3.3.2006, 18:17 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Цитата(Void @ 2.3.2006, 21:17

)

Но, оказывается, ты реализовал обычные бинарные деревья.

Я это самое... того... список забыл отсортировать smile

Задумка была такая:
# Берём дерево
# Делаем из него список
# Модифицируем
# Сортируем
# Выращиваем обратно -- функцией toAvl()

В соответствии с принципом "что, а не как", никто не гарантирует, что это оптимально smile

Void

Дата 3.3.2006, 20:08 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

setq, оригинально smile

Цитата(setq @ 3.3.2006, 20:17

)

никто не гарантирует, что это оптимально

Гонять списки туда и обратно + O(N) сплайсинг списка по номеру элемента… Да, пожалуй ты прав smile

В ближайшие дни постараюсь выкроить часик и дать реализацию на OCaml и, возможно, на C++ или C#.

P.S. Ты бы помимо красных патчей, сам код поправил. А то словно опасаешься инсинуаций каких-то smile

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

setq

Дата 3.3.2006, 21:51 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Код подправил и вставил сортировку в функцию toAvl().

Цитата(Void @ 3.3.2006, 20:08

)

В ближайшие дни постараюсь выкроить часик и дать реализацию на OCaml и, возможно, на C++ или C#.

Окей. Ждём. smile

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Разное тестирование \| Следующая тема »