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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
дополнение
дополнение
Строка 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> и [[Haskell]], причём в последнем оно не входит в стандарт языка '''Haskell-98''', а реализовано только в одном из расширений компилятора [[GHC]].
'''Обобщённый алгебраи́ческий тип да́нных''' (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
| author = Bove, Ana and Dybjer, Peter and Norell, Ulf
| year = 2009
| conference = TPHOLs '09
| title = A Brief Overview of Agda --- A Functional Language with Dependent Types
| booktitle = Proceedings of the 22Nd International Conference on Theorem Proving in Higher Order Logics
| url = http://dx.doi.org/10.1007/978-3-642-03359-9_6
| accessdate = 2013-12-06
| pages = 73--78
| id = Bove:2009:BOA:1616077.1616085
| location = Munich, Germany
| doi = 10.1007/978-3-642-03359-9_6
| publisher = Springer-Verlag
}}</ref> и [[Haskell]], причём в последнем оно не входит в стандарт языка '''Haskell-98''', а реализовано только в одном из расширений компилятора [[GHC]].

Язык Haskell имитирует {{нп2|inductive family|индуктивное семейство}}, представляя их типами, индексированными другими типами<ref name="agda" />.

== Пример на Haskell ==
В следующем примере определяется обобщённый тип <code>Type</code>, в котором представлены несколько типов<ref>{{книга
| автор = Hagiya, M. and Wadler, P.
| заглавие = Functional and Logic Programming: 8th International Symposium, FLOPS 2006, Fuji-Susono, Japan, April 24-26, 2006, Proceedings
| издательство = Springer
| год = 2006
| pages = 17-18
| isbn = 9783540334385
| ref = Hagiya, M. and Wadler, P.
}}</ref>:

<source lang="haskell">
data Type :: * -> * where
Char :: Type Char
Int :: Type Int
List :: Type a -> Type [a] .
</source>

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

<source lang="haskell">
sum :: Type a -> a -> Int
sum Char _ = 0
sum Int n = n
sum (List a) xs = foldr (+) 0 (map (sum a) xs) .
</source>

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

<source lang="haskell">
sum (List Int) [1, 2, 4]
</source>


== Примечания ==
== Примечания ==

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

Обобщённый алгебраи́ческий тип да́нных (GADT, англ. generalized algebraic data type) — один из видов алгебраических типов данных, который характеризуется тем, что его конструкторы могут возвращать значения не своего типа, связанного с ним[1]. Такие типы реализованы в нескольких языках программирования, в частности в языках OCaml (начиная с версии 4)[2], Idris[3], Agda[4] и Haskell, причём в последнем оно не входит в стандарт языка Haskell-98, а реализовано только в одном из расширений компилятора GHC.

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

Пример на Haskell

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

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. ↑ Xavier Leroy. The state of OCaml, 2012 (англ.). OCaml Users and Developers Workshop 4 (14 сентября 2012). Дата обращения: 13 декабря 2014.
  3. ↑ Idris Example
  4. ↑ 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) (ссылка)
  5. ↑ 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=67309806