Rambler's Top100
"Knowledge itself is power"
F.Bacon
Поиск | Карта сайта | Помощь | О проекте | ТТХ  
 Базарная площадь
  
О разделе

Основная страница

Группы обсуждений


Тематический каталог обсуждений

Архив

 
 К н и г и
 
Книжная полка
 
 
Библиотека
 
  
  
 


Поиск
 
Поиск по КС
Поиск в статьях
Яndex© + Google©
Поиск книг

 
  
Тематический каталог
Все манускрипты

 
  
Карта VCL
ОШИБКИ
Сообщения системы

 
Форумы
 
Круглый стол
Новые вопросы

 
  
Базарная площадь
Городская площадь

 
   
С Л С

 
Летопись
 
Королевские Хроники
Рыцарский Зал
Глас народа!

 
  
ТТХ
Конкурсы
Королевская клюква

 
Разделы
 
Hello, World!
Лицей

Квинтана

 
  
Сокровищница
Подземелье Магов
Подводные камни
Свитки

 
  
Школа ОБЕРОНА

 
  
Арсенальная башня
Фолианты
Полигон

 
  
Книга Песка
Дальние земли

 
  
АРХИВЫ

 
 

Сейчас на сайте присутствуют:
 
  
 
Во Флориде и в Королевстве сейчас  23:28[Войти] | [Зарегистрироваться]
Обсуждение темы:
Функциональное программирование

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

Исторически функциональное программирование появилось практически вместе с императивным.
Вторым языком после фортрана был лисп.
Но увы, функциональное программирование надолго было уделом исследовательских институтов или специализированных приложений (Искусственный Интеллект)
Конечно не надо считать весь мир дураками из за того что развитие пошло по пути языков Алгол семейства.
Для этого были вполне обьективные причины. Функциональные языки слишком близки к человеку и слишком далеки от машины.
Они сьедают в десятки раз больше рессурсов чем императивные языки.
Вспомните претензии, предявляемые к java - первому императивному языку с виртуальной машиной и сборщиком мусора, толкаемому большими корпорациями в mainstream.
Жутко тормозит, и жрет всю память какая есть. А ведь функциональные языки (далее ФЯ) все без иключения имеют сборщик мусора, виртуальную машину.
Многие из них (семейство лисп) еще и динамические, что только усугубляет положение.
Вполне естественно что появившись более полусотни лет назад они надолго опередилли свое время.

Для широкого распространения ФЯ нужны гигабайты дешевой памяти и гигагерцы дешевых процессоров.
Прошло более 50 лет, прежде чем такие требования к железу стали реальностью.
Это время наступило. СЕЙЧАС.
Добро пожаловать в новую эру программирования.

 Jack Of Shadows

Количество сообщений на странице

Порядок сортировки сообщений
Новое сообщение вверху списка (сетевая хронология)
Первое сообщение вверху списка (обычная хронология)

Перейти на конкретную страницу по номеру


Всего в теме 5502 сообщения

Добавить свое сообщение

Отслеживать это обсуждение


Смотрите также обсуждения:
Средства разработки. Языки программирования.
  • Delphi 4 or Delphi 5
  • Что приобрести в качестве средства разработки?
  • Delphi6
  • Delphi vs PowerBuilder
  • Сравнение компиляторов
  • Вот и вышла Delphi 7... Вы рады?

  • <<<... | 2112—2103 | 2102—2093 | 2092—2083 | ...>>>
    Всего сообщений в теме: 5502; страниц: 551; текущая страница: 341


    № 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")

    {-------------------------------------------------------------------------------
    -- Преобразовать содержимое входного файла в список [TestCaseStrLn]
    -}

    convert :: String -> [TestCaseStrLn]
    convert s = takeWhile (\(_, tc) -> tc /= the_END)
                          (map  strs'to'TestCaseLn
                                (zip [1..] (str'to'strs s)))
      where
        {-----------------------------------------------------------------
        -- Преобразовать строку символов с разделителями \n в список строк
        -- с учётом возможных пустых строк. Пустые строки отсеять.
        -}

        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

        {--------------------------------------------------------------------------
        -- Преобразовать строку вида "O+ O- ?" в кортёж типа ("O+", "O-", "?")
        -- с учётом неопределённого количества пробелов между группами и после них.
        -- Все пробелы отсеять.
        -}

        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)

    {-------------------------------------------------------------------------------
    -- В такой вот вид нужно перевести входные данные:
    --
    -- [ (1, ("O+",    "O-",    "?")),
    --  (2, ("O+",    "?",    "O-")),
    --  (3, ("AB-",  "AB+",  "?")),
    --  (4, ("AB+",  "?",    "O+"))  ] -->
    --
    -- [ (1, (["O+"],  ["O-"],  ["O+", "O-"])),
    --  (2, (["O+"],  ["A-", "A+", "B-", "B+", "O-", "O+"], ["O-"])),
    --  (3, (["AB-"], ["AB+"], ["A+", "A-", "B+", "B-", "AB+", "AB-"])),
    --  (4, (["AB+"], [],      ["O+"]))                                  ]
    -}

    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 1: O+ O- {O+, O- }

    -- Case 2: O+ {A-, A+, B-, B+, O-, O+} O-
    -- Case 3: AB- AB+ {A+, A-, B+, B-, 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 = " {" ++ show_set 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- {O+, O-}
    Case 2: O+ {A-, A+, B-, B+, O-, O+} O-
    Case 3: AB- AB+ {A+, A-, AB+, AB-, B+, B-}
    Case 4: AB+ IMPOSSIBLE O+


    Эталонный результат:

    Case 1: O+ O- {O+, O-}
    Case 2: O+ {A-, A+, B-, B+, O-, O+} O-
    Case 3: AB- AB+ {A+, A-, B+, B-, 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-}
      O+ ? O-            Case 2: O+ {A-, A+, B-, B+, O-, O+} O-
      AB- AB+ ?          Case 3: AB- AB+ {A+, A-, B+, B-, AB+, AB-}
      AB+ ? O+            Case 4: AB+ IMPOSSIBLE O+
      E N D



    <<<... | 2112—2103 | 2102—2093 | 2092—2083 | ...>>>
    Всего сообщений в теме: 5502; страниц: 551; текущая страница: 341


    Добавить свое сообщение

    Отслеживать это обсуждение

    Дополнительная навигация:
    Количество сообщений на странице

    Порядок сортировки сообщений
    Новое сообщение вверху списка (сетевая хронология)
    Первое сообщение вверху списка (обычная хронология)

    Перейти на конкретную страницу по номеру
      
    Время на сайте: GMT минус 5 часов

    Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter.
    Функция может не работать в некоторых версиях броузеров.

    Web hosting for this web site provided by DotNetPark (ASP.NET, SharePoint, MS SQL hosting)  
    Software for IIS, Hyper-V, MS SQL. Tools for Windows server administrators. Server migration utilities  

     
    © При использовании любых материалов «Королевства Delphi» необходимо указывать источник информации. Перепечатка авторских статей возможна только при согласии всех авторов и администрации сайта.
    Все используемые на сайте торговые марки являются собственностью их производителей.

    Яндекс цитирования