Как вы делаете общее программирование в Haskell?

Question

Исходя из C ++, я считаю, что общее программирование необходимо. Интересно, как люди подходят к этому в Хаскеле?

Скажите, как написать универсальную функцию подкачки в Haskell?

Есть ли в Haskell эквивалентная концепция частичной специализации?

В C ++ я могу частично специализировать универсальную функцию подкачки с помощью специальной для универсального контейнера map / hash_map, в котором есть специальный метод подкачки для O (1) подкачки контейнера. Как вы это делаете в Haskell или каков канонический пример общего программирования в Haskell?

Answer 1

Это тесно связано с вашим другим вопросом о Haskell и быстрой сортировке. Я думаю, что вам, вероятно, нужно прочитать хотя бы введение книги о Хаскелле. Звучит так, как будто вы еще не поняли ключевой момент, который заключается в том, что он запрещает вам изменять значения существующих переменных.

Своп (как он понимается и используется в C ++) по своей сути сводится к изменению существующих значений. Таким образом, мы можем использовать имя для ссылки на контейнер и заменить этот контейнер совершенно другим содержимым, а также специализировать эту операцию, чтобы она была быстрой (и свободной от исключений) для конкретных контейнеров, что позволяет нам реализовывать подход изменения и публикации (крайне важно для написания кода, исключающего исключение, или попытки написать код без блокировки).

Вы можете написать общий своп в Haskell, но он, вероятно, возьмет пару значений и вернет новую пару, содержащую те же значения с обратными позициями, или что-то в этом роде. Не совсем то же самое, и не имеет одинакового использования. Не было бы никакого смысла пытаться специализировать ее для карты, копаясь в этой карте и меняя ее отдельные переменные-члены, потому что вы просто не можете делать такие вещи в Haskell (вы можете выполнять специализацию, но не модификация переменных).

Предположим, мы хотели "измерить" список в Haskell:

measure :: [a] -> Integer

Это объявление типа. Это означает, что функция measure принимает список чего угодно (a является параметром универсального типа, поскольку он начинается со строчной буквы) и возвращает целое число. Так что это работает для списка любого типа элемента - это то, что называется шаблоном функции в C ++ или полиморфной функцией в Haskell (не то же самое, что полиморфный класс в C ++).

Теперь мы можем определить это, предоставив специализации для каждого интересного случая:

measure [] = 0

т.е. измерьте пустой список, и вы получите ноль.

Вот очень общее определение, которое охватывает все другие случаи:

measure (h:r) = 1 + measure r

Бит в скобках на LHS является шаблоном. Это значит: взять список, отрубить голову и назвать его h, назвать оставшуюся часть r. Эти имена являются параметрами, которые мы можем использовать. Это будет соответствовать любому списку с хотя бы одним элементом.

Если вы пробовали метапрограммирование шаблонов в C ++, это все будет для вас старомодно, поскольку в нем используется один и тот же стиль - рекурсия для выполнения циклов, специализация для завершения рекурсии. За исключением того, что в Haskell он работает во время выполнения (специализация функции для определенных значений или шаблонов значений).

Answer 2

Как говорит Earwicker, этот пример не столь значим в Haskell. Если вы все равно хотите это иметь, вот что-то похожее (обмен двух частей пары), c & p из интерактивного сеанса:

GHCi, version 6.8.2: http://www.haskell.org/ghc/  :? for help
Loading package base ... linking ... done.
Prelude> let swap (a,b) = (b,a)
Prelude> swap("hello", "world")
("world","hello")
Prelude> swap(1,2)
(2,1)
Prelude> swap("hello",2)
(2,"hello")

Answer 3

В Haskell функции являются настолько универсальными (полиморфными), насколько это возможно - компилятор выведет «Самый общий тип». Например, пример свопа в TheMarko по умолчанию полиморфен при отсутствии сигнатуры типа:

* Main> let swap (a, b) = (b, a)
* Main>: t swap
swap :: (t, t1) -> (t1, t)

Что касается частичной специализации, ghc имеет расширение не-98:
Файл: /// C: /ghc/ghc-6.10.1/doc/users_guide/pragmas.html#specialize-pragma

Также обратите внимание на несоответствие в терминологии. То, что называется универсальным в c ++, Java и C #, в Haskell называется полиморфным. «Универсальный» в Хаскеле обычно означает политипику: http://haskell.readscheme.org/generic.html
Но, о боже, я использую общий смысл c ++.

Answer 4

В Haskell вы создаете классы типов. Классы типов не похожи на классы в ОО-языках. Возьмем класс Numeric type. Это говорит о том, что все, что является экземпляром класса, может выполнять определенные операции (+ - * /), поэтому Integer является членом Numeric и предоставляет реализации функций, которые необходимо рассматривать как Numeric, и может использоваться везде, где Числовой ожидается.

Скажем, вы хотите иметь возможность искать Ints и Strings. Тогда вы объявите Int и String как экземпляры типа класс Foo. Теперь везде, где вы видите тип (Foo a), теперь вы можете использовать Int или String.

Причина, по которой вы не можете добавлять ints и float напрямую, заключается в том, что add имеет тип (Numeric a) a -> a -> aa - это переменная типа, и, как и обычные переменные, она может быть связана только один раз, так что поскольку вы привязываете его к Int, каждый a в списке должен быть Int.

Answer 5

Прочитав достаточно книги в Haskell, чтобы по-настоящему понять ответ Уорикера, я бы посоветовал вам также прочитать о типовых классах. Я не уверен, что означает «частичная специализация», но похоже, что они могут приблизиться.