Функциональное программирование |
Функциональное программирование всегда привлекало меня в противопоставлении к императивному.
Я очень часто обсуждаю различные аспекты функционального программирования на различных ветках на Базарной площади.
Но хотелось бы собрать всех заинтересованный этой темой в одной ветке.
Я думаю что настало время открыть такую тему. И вот почему.
Исторически функциональное программирование появилось практически вместе с императивным.
Вторым языком после фортрана был лисп.
Но увы, функциональное программирование надолго было уделом исследовательских институтов или специализированных приложений (Искусственный Интеллект)
Конечно не надо считать весь мир дураками из за того что развитие пошло по пути языков Алгол семейства.
Для этого были вполне обьективные причины. Функциональные языки слишком близки к человеку и слишком далеки от машины.
Они сьедают в десятки раз больше рессурсов чем императивные языки.
Вспомните претензии, предявляемые к java - первому императивному языку с виртуальной машиной и сборщиком мусора, толкаемому большими корпорациями в mainstream.
Жутко тормозит, и жрет всю память какая есть. А ведь функциональные языки (далее ФЯ) все без иключения имеют сборщик мусора, виртуальную машину.
Многие из них (семейство лисп) еще и динамические, что только усугубляет положение.
Вполне естественно что появившись более полусотни лет назад они надолго опередилли свое время.
Для широкого распространения ФЯ нужны гигабайты дешевой памяти и гигагерцы дешевых процессоров.
Прошло более 50 лет, прежде чем такие требования к железу стали реальностью.
Это время наступило. СЕЙЧАС.
Добро пожаловать в новую эру программирования.
Jack Of Shadows
Всего в теме 5502 сообщения
Добавить свое сообщение
Отслеживать это обсуждение
- Средства разработки. Языки программирования.
- Delphi 4 or Delphi 5
- Что приобрести в качестве средства разработки?
- Delphi6
- Delphi vs PowerBuilder
- Сравнение компиляторов
- Вот и вышла Delphi 7... Вы рады?
№ 2102 18-03-2007 04:28 | |
Ответ на »сообщение 3291« (AVC)
Я просто (как новичок в ФП) пытаюсь подойти к каррингу "с практической точки зрения", для лучшего понимания.
Хотите простой в лоб пример на кой ляд нужен это карринг:
count a xs = length (filter (== a) xs)
Функция count считает сколько элементов a в списке xs
Для этого сначала функция filter выбирает из списка xs все элементы равные a,
а затем функция length возвращает длину нового списка в котором все элементы а
Так вот функции filter нужно передавать функцию сравнения. Заметьте странную конструкцию (== a) которая пережается ей в виде функции сравнения. Это карринг функции ==, у которой уже задан один аргумент.
Если бы не было кааринга то пришлось бы писать вот так неуклюже:
count a xs = length (filter equala xs)
where equala x = x == a
Ну или при помощи лямбды, что тоже не так красиво и читабельно как карринг.
Еще примеры карринга:
Найти в списке все элементы больше 5
filter (>5) xs
Каждый элемент списка умножить на 2:
map (*2) xs
Разбить список на три списка с элементами меньше 10, равным 10 и больше 10
map (`filter` xs) [(<10), (==10), (>10)]
Так ЯСНО, и КОРОТКО без карринга не запишешь.
№ 2101 17-03-2007 20:24 | |
Два интересных наблюдения из приведенного кода.
Во первых читать код на хаскеле лично мне было гораздо легче.
Илье почему то кажется что если он не знает немецкий то немецкий читать гораздо труднее чем русский :))
Во вторых разница в размере кода новичка-хаскелиста и зубра-оберониста практически в два раза, показывает что в условиях соревнований у хаскелистов будет колоссальное преимущество в скорости.
Что опять таки утверждает меня в моем мнении что разреши в соревнованиях хаскель, окамл, лисп - и о гегемонии ИЯ на соревнованиях можно забыть.
Проигрывать то никому неохота :))
№ 2100 17-03-2007 17:43 | |
Ответ на »сообщение 2099« (Geniepro)
___________________________
Сочувтствую. А с Оперой проблем нет?
Если вы скажете моему шефу что кроме IE и Firefox существует еще и опера и сафари, не пожалею годовую зарплату и найму на вас килера :))
№ 2099 17-03-2007 12:27 | |
Ответ на »сообщение 2098« (Jack Of Shadows)
___________________________
Однако у вас прорва свободного времени. :))
Я даже в субботу вынужден заниматься идиосинкразиями различий IE и Firefox. Нужно поддерживать оба браузера :(((
Сочувтствую. А с Оперой проблем нет?
Было бы неплохо увмдеть решения на Лиспе/Scheme, только у Вас, похоже, времени на это не будет, а лисперов у нас тут маловато...
Кстати я бы вам посоветовал оформить примеры в ряд статей на ЖЖ.
Здесь они пропадут.
Да, я об этом тоже думал, но пока рано ещё.
С другой стороны, там можно бросить вызов другим программерам, а заодно на разные варианты на разных языках посмотреть... ;о)
№ 2098 17-03-2007 11:51 | |
Ответ на »сообщение 2095« (Geniepro)
___________________________
Кстати я бы вам посоветовал оформить примеры в ряд статей на ЖЖ.
Здесь они пропадут.
№ 2097 17-03-2007 11:40 | |
Ответ на »сообщение 2095« (Geniepro)
___________________________
Однако у вас прорва свободного времени. :))
Я даже в субботу вынужден заниматься идиосинкразиями различий IE и Firefox. Нужно поддерживать оба браузера :(((
№ 2096 17-03-2007 10:48 | |
Ответ на »сообщение 2095« (Geniepro)
___________________________
В связи с этим прошу модераторов удалить моё предыдущее сообщение
Извиняюсь, но я попарился с ссылкой.
Прошу модераторов удалить моё сообщение № 2094 в этой теме.
№ 2095 17-03-2007 10:39 | |
Обнаружил странный глюк, связанный с разным пониманием кодировок ANSI/UTF-8 разными трансляторами Хаскелла, исправил и обновил код на Хаскелле.
В связи с этим прошу модераторов удалить моё предыдущее сообщение
ЗЫ. Проблема была из-за того, что функция openFileC имела последнюю букву С кириллическую, а не латинскую. Начертание у них одинаковое, а коды - разные. WinHUGS принимал файл в кодировке ANSI без проблем, GHC отвергал. В кодировке UTF-8 - наоборот, GHC нормально принимал, а WinHUGS ругался...
ЗЗЫ. Мдя, всё-таки идентификаторы должны записываться латинницей!!!
[BR]
А вот и примерное решение этой задачи на Хаскелле.
Поскольку я всего лишь "a little haskeller", то наверняка этот код можно улучшить, в смысле упростить. Но, в принципе, работает...
module ACM_2007_A where
import IO
type TestCaseStr = (String, String, String)
type TestCaseStrLn = (Int, TestCaseStr)
type TestCase = (SetABO, SetABO, SetABO)
type TestCaseLn = (Int, TestCase)
type SetABO = [String]
--------------------------------------------------------------------------------
main = do fromHandle <- openFileC "blood.in" ReadMode
contents <- hGetContents fromHandle
showTestCaseLn $ process $ convert contents -- собственно расчёт
hClose fromHandle
--------------------------------------------------------------------------------
openFileC :: String -> IOMode -> IO Handle
openFileC name mode =
do catch (openFile name mode)
(\_ -> error $ "Cannot open file "++ name ++ "\n")
convert :: String -> [TestCaseStrLn]
convert s = takeWhile (\(_, tc) -> tc /= the_END)
(map strs'to'TestCaseLn
(zip [1..] (str'to'strs s)))
where
str'to'strs :: String -> [String]
str'to'strs s = to_strs s [] []
where
to_strs [ ] v w = filter ([]/=) $ reverse (reverse v : w)
to_strs ('\n':cs) v w = to_strs cs [] (reverse v : w)
to_strs ( c :cs) v w = to_strs cs (c:v) w
strs'to'TestCaseLn :: (Int, String) -> TestCaseStrLn
strs'to'TestCaseLn (ln, s) = to_tc s True [] []
where
to_tc [ ] _ v w = tc $ filter (""/=) $ reverse (reverse v : w)
to_tc (' ':cs) True v w = to_tc cs False [] (reverse v : w)
to_tc (' ':cs) False _ w = to_tc cs False [] w
to_tc ( c :cs) _ v w = to_tc cs True (c:v) w
tc [m, p, c] = (ln, (m, p, c))
tc _ = error $ "Incorrect number of blood types in line "
++ show ln ++ ":\n\n" ++ s ++ "\n"
--------------------------------------------------------------------------------
the_END = ("E", "N", "D") -- Завершитель входного файла
allels'from'ABO "A" = [ "A", "O" ]
allels'from'ABO "B" = [ "B", "O" ]
allels'from'ABO "AB" = [ "A", "B" ]
allels'from'ABO "O" = [ "O" ]
abo'from'allels "AA" = "A"
abo'from'allels "AO" = "A"
abo'from'allels "OA" = "A"
abo'from'allels "BB" = "B"
abo'from'allels "BO" = "B"
abo'from'allels "OB" = "B"
abo'from'allels "AB" = "AB"
abo'from'allels "BA" = "AB"
abo'from'allels "OO" = "O"
allels'from'Rh "+" = [ "+", "-" ]
allels'from'Rh "-" = [ "-" ]
rh'from'allels "++" = "+"
rh'from'allels "+-" = "+"
rh'from'allels "-+" = "+"
rh'from'allels "--" = "-"
all'blood'types = [ abo ++ rh | abo <- [ "A", "AB", "B", "O" ],
rh <- [ "-", "+" ] ]
get_allels :: Int -> String -> (SetABO, SetABO)
get_allels _ (a:l:r:[]) = (allels'from'ABO (a:[l]), allels'from'Rh [r])
get_allels _ (a:r:[]) = (allels'from'ABO ([a]), allels'from'Rh [r])
get_allels ln err = error $ "Incorrect blood type in line "
++ show ln ++ ":\n\n" ++ err ++ "\n"
sieve :: (Eq a) => [a] -> [a]
sieve (x:xs) = sievet xs [x]
where
sievet [ ] w = reverse w
sievet (y:ys) w = sievet ys (if y `elem` w then w else y:w)
process :: [TestCaseStrLn] -> [TestCaseLn]
process tcs = map (\(ln, var) -> (ln, calculate ln var)) tcs
where
calculate :: Int -> TestCaseStr -> TestCase
calculate ln ( m, p, "?") = ([m], [p], calc_child ln m p)
calculate ln ( m, "?", c ) = ([m], calc_parent ln m c, [c])
calculate ln ("?", p, c ) = (calc_parent ln p c, [p], [c])
calculate ln err = error $ "Incorrect test case in line "
++ show ln ++ ":\n\n" ++ show err ++ "\n"
calc_child :: Int -> String -> String -> SetABO
calc_child ln mama papa = [ abo ++ rh | abo <- c_abo, rh <- c_Rh ]
where
(m_abo, m_Rh) = get_allels ln mama
(p_abo, p_Rh) = get_allels ln papa
c_abo = sieve $ map abo'from'allels [ m ++ p | m <- m_abo, p <- p_abo ]
c_Rh = sieve $ map rh'from'allels [ m ++ p | m <- m_Rh, p <- p_Rh ]
calc_parent :: Int -> String -> String -> [String]
calc_parent ln parent child = filter possible all'blood'types
where
possible bt = child `elem` (calc_child ln parent bt)
-- Case 2: O+ O-
-- Case 3: AB- AB+
-- Case 4: AB+ IMPOSSIBLE O+
-}
showTestCaseLn :: [TestCaseLn] -> IO ()
showTestCaseLn tcs = foldr (>>) (return ()) $ map (putStrLn.show_tc) tcs
where
show_tc :: TestCaseLn -> String
show_tc (ln, (m, p, c)) = "Case " ++ show ln ++ ":" ++ show_SetABO m
++ show_SetABO p ++ show_SetABO c
where
show_SetABO [ ] = " IMPOSSIBLE" -- Нет вариантов
show_SetABO [a] = ' ':a -- Один вариант
show_SetABO set = " " -- Куча вариантов
where
show_set [c] = c
show_set (c:cs) = c ++ ',':' ':show_set cs
Входной файл blood.in :
O+ O- ?
O+ ? O-
AB- AB+ ?
AB+ ? O+
E N D
Результат:
Case 1: O+ O-
Case 2: O+ O-
Case 3: AB- AB+
Case 4: AB+ IMPOSSIBLE O+
Эталонный результат:
Case 1: O+ O-
Case 2: O+ O-
Case 3: AB- AB+
Case 4: AB+ IMPOSSIBLE O+
Результаты выводятся не совсем в том порядке, что в примере ( {A+, A-, AB+, AB-, B+, B-} вместо {A+, A-, B+, B-, AB+, AB-} ), но, как я понимаю, это не критично, поскольку в условиях задачи не сказано, как именно сортировать выходные данные, просто сказано, что формат вывода должен быть похожим на пример.
№ 2094 Удалено модератором | |
№ 2093 17-03-2007 08:34 | |
По предложению Руслана Богатырёва в соседней теме
Первая задача из списка задач олимпиады %url[ACM ICPC 2007 Final] http://icpc.baylor.edu/icpc/Finals/2007WorldFinalProblemSet.pdf
"Problem A+. Consanguine Calculations"
Задача А+
Анализ кровнородственности
Входной файл: blood.in
Кровь любого человека имеет 2 маркера, называемых ABO-аллелями. Каждый маркер представляется одной из трёх букв: A, B или O. Это даёт шесть возможных комбинаций аллелей, которые могут быть у человека, каждая из которых может характеризовать группу крови ABO этого человека.
Комбинация Группа крови ABO
~~~~~~~~~~ ~~~~~~~~~~~~~~~~
AA A
AB AB
AO A
BB B
BO B
OO O
Также каждый человек имеет две аллели резус-фактора крови Rh, представленных символами + и -. У тех, у кого Rh-положительный (Rh+), имеется от одной до двух аллелей +. У тех, у кого Rh-отрицательный, обе аллели всегда -.
Тип крови человека - это комбинация группы крови ABO и резус-фактора Rh. Тип крови записывается обозначением группы крови с суффиксом + или -, обозначающим резус-фактор, например, A+, AB-, O-.
Типы крови наследуются - каждый биологический родитель передаёт своему ребёнку одну ABO-аллель (случайно выбираемую из его двух) и одну аллель резус-фактора. Таким образом, две ABO-аллели и две аллели резус-фактора родителей определяют тип крови ребёнка. Например, если оба родителя имеют тип крови А-, то ребёнок может иметь любой из двух типов: А- или О-. У родителей с типами А+ и В+ ребёнок может иметь любой тип крови.
В этой задаче даются типы крови обоих родителей или одного из родителей и ребёнка; требуется получить (возможно пустое) множество типов крови, которые могут быть у ребёнка или у другого родителя.
Примечание: прописная буква "О" используется в этой задаче для обозначения типа крови, а не цифры 0.
Входные данные:
~~~~~~~~~~~~~~~
Входные данные состоят из множества тестовых вариантов. Каждый вариант - это одна строка в таком формате: тип крови одного родителя, тип крови другого родителя и, наконец, тип крови ребёнка, за исключением того, что тип крови одного из родителей или ребёнка заменяется знаком вопроса. Для улучшения читаемости в любом месте строки может быть помещён пробел, за исключением спецификации типа крови.
За последний тестовым вариантом следует строка с буквами "E", "N" и "D", разделёнными пробелами.
Выходные данные:
~~~~~~~~~~~~~~~~
Для каждого тестового варианта требуется распечатать номер теста (начинающегося с 1) и типы крови родителей и ребёнка. Если нет возможного для родителя типа крови, распечатать “IMPOSSIBLE”. Если для родителей или ребёнка возможны несколько вариантов типов крови, распечатать все возможные варианты в виде списка значения, разделённых запятыми, и заключённого в фигурные скобки.
Пример вывода иллюстрирует несколько выходных форматов. Ваш формат вывода должен быть похожим.
Sample Input Output for the Sample Input
~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~
O+ O- ? Case 1: O+ O-
O+ ? O- Case 2: O+ O-
AB- AB+ ? Case 3: AB- AB+
AB+ ? O+ Case 4: AB+ IMPOSSIBLE O+
E N D
Добавить свое сообщение
Отслеживать это обсуждение
Дополнительная навигация: |
|