trait + impl vs class , навеяно Rust'ом

[applegame]

Ладно. Мы опять скатились не туда куда нужно. Я пытался понять как работают дженерики в Java и как выполнить тайп-чек рекурсивной функции-дженерика без бесконечного раскрытия типов?

[korvin]

Цитата applegame @ 12.07.15, 20:44

Ведь и в Хаскелле можно в некотором роде "специализировать" уже написанные полиморфные функции.

Нельзя. Попробуй специализировать

map :: (a -> b) -> [a] -> [b]

Цитата applegame @ 12.07.15, 20:44

Например для того чтобы мой тип Foo мог участвовать в операциях сложения мне придется написать инстанс Num для Foo, в котором специализировать сложение для этого самомго Foo. Ведь так?

Так, и это не имеет отношения к ПП. Это два разных механизма. Также как ПП и классы в Ocaml, F#, Scala, например.

[D_KEY]

Цитата applegame @ 12.07.15, 20:57

И как это сделать не разворачивая рекурсию типов до упора?

Так же, как в java, c# и haskell.

Цитата

Хотя нет не любую. Только те, которые в тайп-классах.

Именно так, да. И это специальный полиморфизм.

Добавлено 12.07.15, 21:18

Цитата D_KEY @ 12.07.15, 21:16

Цитата applegame @ 12.07.15, 20:57

И как это сделать не разворачивая рекурсию типов до упора?

Так же, как в java, c# и haskell.

Как и в этих языках, в Rust дженерики являются средством ПП. И в rust нет перегрузки функций и специализации дженерик функций/типов.

[applegame]

Интересное кино. Читаем на https://wiki.haskell.org/Polymorphism:

Цитата

Parametric polymorphism refers to when the type of a value contains one or more (unconstrained) type variables, so that the value may adopt any type that results from substituting those variables with concrete types.
In Haskell, this means any type in which a type variable, denoted by a name in a type beginning with a lowercase letter, appears without constraints (i.e. does not appear to the left of a =>).

Смотрим на код задачи:

module Test where
data Nil = Nil
data Cons a = Cons Integer a
class ScalarProduct a where scalarProduct :: a -> a -> Integer
instance ScalarProduct Nil where scalarProduct Nil Nil = 0
instance ScalarProduct a => ScalarProduct (Cons a) where scalarProduct (Cons n1 a1) (Cons n2 a2) = n1 * n2 + scalarProduct a1 a2
main :: Integer -> Integer
main n = main' n 0 Nil Nil where
  main' :: ScalarProduct a => Integer -> Integer -> a -> a -> Integer
  main' 0 _ as bs = scalarProduct as bs
  main' n i as bs = main' (n-1) (i+1) (Cons (2*i+1) as) (Cons (i^2) bs)

Таки получается, что функция main' - не полиморфна, так как есть ограничение ScalarProduct a.

Добавлено 12.07.15, 21:53
И еще вот. Паттерн-матчинг в Хаскеле - это ad-hoc полиморфизм?

[korvin]

Цитата applegame @ 12.07.15, 21:38

Таки получается, что функция main' - не полиморфна, так как есть ограничение ScalarProduct a.

Не параметрически полиморфна, да. Я тебе это сказал ещё про твой первый пример.

Цитата applegame @ 12.07.15, 21:38

И еще вот. Паттерн-матчинг в Хаскеле - это ad-hoc полиморфизм?

Паттерн-матчинг вообще никакого отношения к какому бы то ни было полиморфизму не имеет, это (почти) обычный switch/case.

Сообщение отредактировано: korvin - 12.07.15, 22:05

[applegame]

Цитата korvin @ 12.07.15, 22:04

Паттерн-матчинг вообще никакого отношения к какому бы то ни было полиморфизму не имеет, это (почти) обычный switch/case.

По типу паттерн-матчинга не бывает?

Добавлено 12.07.15, 22:13
Вернемся к жабе. Как там разруливается полиморфная рекурсия и возможна ли реализация такой возможности в C++?

[korvin]

Цитата applegame @ 12.07.15, 22:09

По типу паттерн-матчинга не бывает?

Нет.

Добавлено 12.07.15, 22:13

Цитата applegame @ 12.07.15, 22:09

полиморфная рекурсия

Что это?

[applegame]

Цитата korvin @ 12.07.15, 22:13

Что это?

- https://en.wikipedia.org/wiki/Polymorphic_recursion
То самое обо что спотыкаются решения задачи на C++/D/Rust.

Сообщение отредактировано: applegame - 12.07.15, 22:17

[korvin]

Java.

[applegame]

D даже сам тип Nested не осиливает

[DarkEld3r]

Цитата D_KEY @ 12.07.15, 19:52

trait в Rust вполне тип.

Тут можно поспорить. Как по мне, то растовые трейты просто выступают одновременно и "тайпклассами" и "интерфейсами".

Цитата D_KEY @ 12.07.15, 20:24

Меня, честно говоря, больше всего удивляет тут Rust. Возможно я чего-то не понимаю, но Rust должен справляться с этой задачей, не смотря на генерацию в реализации.

Каким образом?

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

[Qraizer]

Я бы не очень доверял этой информации касательно выводов.

Цитата

The key disadvantage of monomorphizing code is that destroys separate compilation. In particular, it's impossible to compile a polymorphic library (say, the list library) separate from the clients.

Экспорт шаблонов, т.е. модель разделения, был реализован в Плюсах самым первым, т.е. до модели включения, что и послужило основной причиной оставить его в C++98. Но даже и без экспорта создание библиотек более чем возможно. Только нафик не нужно, ибо жутко неудобно.

[applegame]

Цитата DarkEld3r @ 12.07.15, 23:29

Вот ещё информация по теме.

Весьма интересная информация. Авторы этого документа считают, что мономорфизация - это реализация полиморфизма, со своими преимуществами и недостатками. И, внезапно, MLton - компилятор Standard ML тоже использует мономорфизацию. И, насколько я понял, Standard ML не поддерживает полиморфную рекурсию.

Добавлено 13.07.15, 06:20

Цитата Qraizer @ 13.07.15, 01:59

Экспорт шаблонов, т.е. модель разделения, был реализован в Плюсах самым первым, т.е. до модели включения, что и послужило основной причиной оставить его в C++98. Но даже и без экспорта создание библиотек более чем возможно. Только нафик не нужно, ибо жутко неудобно.

Ну это все же полумера. Экспортировать шаблон целиком никак нельзя, только конечное число его специализаций.

[D_KEY]

Цитата applegame @ 12.07.15, 22:58

D даже сам тип Nested не осиливает

А ты чего ожидал?

Добавлено 13.07.15, 07:56

Цитата DarkEld3r @ 12.07.15, 23:29

Цитата D_KEY @ 12.07.15, 19:52

trait в Rust вполне тип.

Тут можно поспорить. Как по мне, то растовые трейты просто выступают одновременно и "тайпклассами" и "интерфейсами".

Это интерфейсы(которые в Rust типы), которые можно использовать для ограничения дженериков(как и в Java, например).

Добавлено 13.07.15, 08:00

Цитата DarkEld3r @ 12.07.15, 23:29

Цитата D_KEY @ 12.07.15, 20:24

Меня, честно говоря, больше всего удивляет тут Rust. Возможно я чего-то не понимаю, но Rust должен справляться с этой задачей, не смотря на генерацию в реализации.

Каким образом?

Поскольку сами правила типизации в языке не содержат ничего, что бы заставляло инстанцировать типы бесконечно, можно тайпчекать без рекурсивного инстанцирования, как в Java. А вот при генерации кода, если возможно и нужно, генерировать специализации. Подобные рекурсивные штуки в принципе, ни в каком из языков, не смогут использовать данные на стеке, то нам все равно понадобится куча и хранить мы так или иначе будем ссылки, а значит можно обойтись без генерации инстансов.

[applegame]

Цитата D_KEY @ 13.07.15, 07:54

А ты чего ожидал?

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

Цитата D_KEY @ 13.07.15, 07:54

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

Да вроде как DarkEld3r говорил, что содержат. Тем не менее Rust вполне себе параметрически полиморфен, как и C++/D. А эта ваша полиморфная рекурсия, на самом деле, никому не сдалась.

Сообщение отредактировано: applegame - 13.07.15, 10:06