Ответ на »сообщение 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)]

Так ЯСНО, и КОРОТКО без карринга не запишешь.

Два интересных наблюдения из приведенного кода.
Во первых читать код на хаскеле лично мне было гораздо легче.
Илье почему то кажется что если он не знает немецкий то немецкий читать гораздо труднее чем русский :))

Во вторых разница в размере кода новичка-хаскелиста и зубра-оберониста практически в два раза, показывает что в условиях соревнований у хаскелистов будет колоссальное преимущество в скорости.
Что опять таки утверждает меня в моем мнении что разреши в соревнованиях хаскель, окамл, лисп - и о гегемонии ИЯ на соревнованиях можно забыть.
Проигрывать то никому неохота :))

Ответ на »сообщение 2099« (Geniepro)
___________________________
Сочувтствую. А с Оперой проблем нет?
Если вы скажете моему шефу что кроме IE и Firefox существует еще и опера и сафари, не пожалею годовую зарплату и найму на вас килера :))

Ответ на »сообщение 2098« (Jack Of Shadows)
___________________________

Однако у вас прорва свободного времени. :))
Я даже в субботу вынужден заниматься идиосинкразиями различий IE и Firefox. Нужно поддерживать оба браузера :(((

Сочувтствую. А с Оперой проблем нет?

Было бы неплохо увмдеть решения на Лиспе/Scheme, только у Вас, похоже, времени на это не будет, а лисперов у нас тут маловато...


Кстати я бы вам посоветовал оформить примеры в ряд статей на ЖЖ.
Здесь они пропадут.

Да, я об этом тоже думал, но пока рано ещё.
С другой стороны, там можно бросить вызов другим программерам, а заодно на разные варианты на разных языках посмотреть... ;о)

Ответ на »сообщение 2095« (Geniepro)
___________________________
Кстати я бы вам посоветовал оформить примеры в ряд статей на ЖЖ.
Здесь они пропадут.

Ответ на »сообщение 2095« (Geniepro)
___________________________
Однако у вас прорва свободного времени. :))
Я даже в субботу вынужден заниматься идиосинкразиями различий IE и Firefox. Нужно поддерживать оба браузера :(((

Ответ на »сообщение 2095« (Geniepro)
___________________________

В связи с этим прошу модераторов удалить моё предыдущее сообщение

Извиняюсь, но я попарился с ссылкой.
Прошу модераторов удалить моё сообщение № 2094 в этой теме.

Обнаружил странный глюк, связанный с разным пониманием кодировок 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-} ), но, как я понимаю, это не критично, поскольку в условиях задачи не сказано, как именно сортировать выходные данные, просто сказано, что формат вывода должен быть похожим на пример.

По предложению Руслана Богатырёва в соседней теме

Первая задача из списка задач олимпиады %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