Обобщённый алгебраический тип данных: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
дополнение
дополнение
Строка 1: Строка 1:
{{К удалению|2014-12-13}}
{{К удалению|2014-12-13}}
'''Обобщённый алгебраи́ческий тип да́нных''' (GADT, {{lang-en|generalized algebraic data type}}) — один из видов [[алгебраический тип данных|алгебраических типов данных]], который характеризуется тем, что его конструкторы могут возвращать значения не своего типа, связанного с ним{{sfn|Koopman, Plasmeijer, Swierstra|2009|pp=178-179}}. Такие типы реализованы в нескольких языках программирования, в частности в языках [[OCaml]] (начиная с версии 4)<ref>{{cite web|url=http://oud.ocaml.org/2012/slides/oud2012-leroy-slides.pdf|title=The state of OCaml, 2012|author=Xavier Leroy|date=2012-09-14|work=OCaml Users and Developers Workshop|pages=4|lang=en|accessdate=2014-12-13}}</ref>, [[Idris (язык программирования)|Idris]]<ref>[http://www.idris-lang.org/example/ Idris Example]</ref>, [[Agda]]<ref name="agda">{{cite conference
'''Обобщённый алгебраи́ческий тип да́нных''' (GADT, {{lang-en|generalized algebraic data type}}) — один из видов [[алгебраический тип данных|алгебраических типов данных]], который характеризуется тем, что его конструкторы могут возвращать значения не своего типа, связанного с ним{{sfn|Koopman, Plasmeijer, Swierstra|2009|pp=178-179}}. Обобщённые АТД были придуманы под влиянием работ об индуктивных семействах в среде исследователей [[Зависимый тип|зависимых типов]]<ref>{{книга
| автор = Schmid, U. and Kitzelmann, E. and Plasmeijer, R.
| заглавие = Approaches and Applications of Inductive Programming: Third International Workshop, AAIP 2009, Edinburgh, UK, September 4, 2009, Revised Papers
| издательство = Springer
| год = 2010
| allpages =
| pages = 114-115
| isbn = 9783642119309
| ref = Schmid, Kitzelmann, Plasmeijer
}}</ref>.

Такие типы реализованы в нескольких языках программирования, в частности в языках [[OCaml]] (начиная с версии 4)<ref>{{cite web|url=http://oud.ocaml.org/2012/slides/oud2012-leroy-slides.pdf|title=The state of OCaml, 2012|author=Xavier Leroy|date=2012-09-14|work=OCaml Users and Developers Workshop|pages=4|lang=en|accessdate=2014-12-13}}</ref>, [[Idris (язык программирования)|Idris]]<ref>[http://www.idris-lang.org/example/ Idris Example]</ref>, [[Agda]]<ref name="agda">{{cite conference
| author = Bove, Ana and Dybjer, Peter and Norell, Ulf
| author = Bove, Ana and Dybjer, Peter and Norell, Ulf
| year = 2009
| year = 2009

Версия от 10:20, 13 декабря 2014

Обобщённый алгебраи́ческий тип да́нных (GADT, англ. generalized algebraic data type) — один из видов алгебраических типов данных, который характеризуется тем, что его конструкторы могут возвращать значения не своего типа, связанного с ним[1]. Обобщённые АТД были придуманы под влиянием работ об индуктивных семействах в среде исследователей зависимых типов[2].

Такие типы реализованы в нескольких языках программирования, в частности в языках OCaml (начиная с версии 4)[3], Idris[4], Agda[5] и Haskell, причём в последнем оно не входит в стандарт языка Haskell-98, а реализовано только в одном из расширений компилятора GHC.

Язык Haskell имитирует индуктивное семейство (англ. inductive family), представляя их типами, индексированными другими типами[5].

Пример на Haskell

В следующем примере определяется обобщённый тип Type, в котором представлены несколько типов[6]: 

data Type :: * -> * where
    Char :: Type Char
    Int :: Type Int
    List :: Type a -> Type [a] .

Для этого типа можно составить ad hoc-полиморфную функцию суммирования: 

sum :: Type a -> a -> Int
sum Char _ = 0
sum Int n = n
sum (List a) xs = foldr (+) 0 (map (sum a) xs) .

Которую можно применять для типов, поддерживаемых Type, например, для типа [Int]: 

sum (List Int) [1, 2, 4]

Примечания

  1. ↑ Koopman, Plasmeijer, Swierstra, 2009, pp. 178-179.
  2. ↑ Schmid, U. and Kitzelmann, E. and Plasmeijer, R. Approaches and Applications of Inductive Programming: Third International Workshop, AAIP 2009, Edinburgh, UK, September 4, 2009, Revised Papers. — Springer, 2010. — P. 114-115. — ISBN 9783642119309.
  3. ↑ Xavier Leroy. The state of OCaml, 2012 (англ.). OCaml Users and Developers Workshop 4 (14 сентября 2012). Дата обращения: 13 декабря 2014.
  4. ↑ Idris Example
  5. ↑ 1 2 Bove, Ana and Dybjer, Peter and Norell, Ulf (2009). "A Brief Overview of Agda --- A Functional Language with Dependent Types". Proceedings of the 22Nd International Conference on Theorem Proving in Higher Order Logics. TPHOLs '09. Munich, Germany: Springer-Verlag. pp. 73--78. doi:10.1007/978-3-642-03359-9_6. Bove:2009:BOA:1616077.1616085. Дата обращения: 6 декабря 2013. {{cite conference}}: Неизвестный параметр |booktitle= игнорируется (|book-title= предлагается) (справка)Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
  6. ↑ Hagiya, M. and Wadler, P. Functional and Logic Programming: 8th International Symposium, FLOPS 2006, Fuji-Susono, Japan, April 24-26, 2006, Proceedings. — Springer, 2006. — P. 17-18. — ISBN 9783540334385.

Литература

  • Koopman, P. and Plasmeijer, R. and Swierstra, D. Advanced Functional Programming: 6th International School, AFP 2008, Heijen, The Netherlands, May 19-24, 2008, Revised Lectures. — Springer, 2009. — 331 p. — ISBN 9783642046513.
Источник — https://ru.wikipedia.org/w/index.php?title=Обобщённый_алгебраический_тип_данных&oldid=67310029