LINUX.ORG.RU

Список из значений определённых type classes в Haskell (Bounded a, Enum a, Ord a) => [a]

 , , polymorphism


0

4

Всем привет.

Мне нужен список в Haskell, хранящий не какие-то конкретные типы, а абстрактные типы, являющиеся инстансами type классов. Например, объявить список из Eq и класть в него любой тип, который является инстансом Eq. Что-то слышал про existential types, h-lists, но не знаю, куда конкретно копать.

Понадобилось для примера ниже: имеем набор типов (Bounded a, Enum a, Ord a) => a , и это позволяет определять для каждого из них переполнение. На вход функции передаём [a, b, c, d] и, если при инкрементации a происходит переполнение, то оно автоматически передаётся в b и так далее.

import Control.Monad.Trans.State.Lazy

groupSuccWithCarry :: (Bounded a, Enum a, Ord a) => [a] -> [a]
groupSuccWithCarry (h : t) = let (carry, h') = succWithCarry h
                             in h' : evalState (carryOver t) carry

succWithCarry :: (Bounded a, Enum a, Ord a) => a -> (Bool, a)
succWithCarry x = let overflow = x == maxBound
                  in (overflow, if overflow then minBound else succ x)

carryOver :: (Bounded a, Enum a, Monad m, Ord a) => [a] -> StateT Bool m [a]
carryOver = mapM (\x -> do carry <- get
                           let (carry', x') = if carry then succWithCarry x else (False, x)
                           put carry'
                           return $ x')

Для

> data DayOfWeek = Sun | Mon | Tue | Wed | Thu | Fri | Sat deriving (Bounded, Enum, Eq, Ord, Show)
> groupSuccWithCarry [Sat, Sat, Fri, Sun, Wed]
  [Sun, Sun, Sat, Sun, Wed]

работает, но нужна возможность передавать в ф-ию значения разных типов, лишь бы для них были определены соответствующие type классы.

★★★★

Мне нужен список в Haskell, хранящий не какие-то конкретные типы, а абстрактные типы, являющиеся инстансами type классов.

Экзистенциальные типы: Оператор new возвращает указатели на экземпляры разных классов в зависимости от параметров конструктора. Возможно ли? (комментарий)

dmfd
()
Ответ на: комментарий от buddhist

А на сишке ещё проще: кастуешь указатель в void* !

dmfd
()

В хацкеле все примеры надуманные?

anonymous
()
Ответ на: комментарий от dmfd

Немного повозился с existential types, но не могу понять, как мне вызвать minBound, maxBound, succ, (==) на содержимом и как создать экземпляр?

data BEO = forall a. (Bounded a, Enum a, Ord a) => BEO a
> BEO 123

<interactive>:129:1:
    Ambiguous type variable `a0' in the constraints:
      (Bounded a0) arising from a use of `BEO' at <interactive>:129:1-3
      (Enum a0) arising from a use of `BEO' at <interactive>:129:1-3
      (Num a0) arising from the literal `123' at <interactive>:129:5-7
      (Ord a0) arising from a use of `BEO' at <interactive>:129:1-3
    Probable fix: add a type signature that fixes these type variable(s)
    In the expression: BEO 123
    In an equation for `it': it = BEO 123

> data DayOfWeek = Sun | Mon | Tue | Wed | Thu | Fri | Sat deriving (Bounded, Enum, Eq, Ord, Show)
> BEO Sun

<interactive>:133:1:
    No instance for (Show BEO)
      arising from a use of `print'
    Possible fix: add an instance declaration for (Show BEO)
    In a stmt of an interactive GHCi command: print it

Если сделать

instance Show BEO where
  show beo = "beo"

то

> BEO Sun

<interactive>:136:1:
    Overlapping instances for Show BEO
      arising from a use of `print'
    Matching instances:
      instance Show BEO -- Defined at /tmp/group-succ.hs:8:10
      instance Show BEO -- Defined at /tmp/group-succ.hs:8:10
    In a stmt of an interactive GHCi command: print it
Bohtvaroh ★★★★
() автор топика
Ответ на: комментарий от dmfd

P.S. Потому что 123 - полиморфная штука (не знаю как правильно его назвать), а по умолчанию оно будет считаться Integer, который не является экземпляром Bounded.

dmfd
()
Ответ на: комментарий от dmfd

Ага. Хорошо, но по-моему дальше ничего не получится: мне же нужно в конечном итоге распаковать значения назад, а с existential types это невозможно. Плюс непонятно, как вызывать ф-ии из Bounded, Eq, Ord. То есть упаковать в список я смогу, но потом тупик.

Посмотрю h-list...

Bohtvaroh ★★★★
() автор топика
Последнее исправление: Bohtvaroh (всего исправлений: 1)
Ответ на: комментарий от Bohtvaroh

Плюс непонятно, как вызывать ф-ии из Bounded, Eq, Ord.

Примерно так:

f :: BEO -> Bool
f (BEO x) = x<maxBound

C Enum несколько сложнее:

f :: BEO -> BEO
f (BEO x) = BEO $ succ x

мне же нужно в конечном итоге распаковать значения назад

Боюсь, это в принципе невозможно. Сдаётся мне, то что вы хотите сделать, требует динамической типизации.

Можно ещё в сторону Data.Dynamic посмотреть, но там «распаковывать» придётся каждый тип руками.

dmfd
()
Ответ на: комментарий от Bohtvaroh

нужно в конечном итоге распаковать значения назад

То есть нужно что-то кроме «протоколов» классов, указанных после forall? Можно пример поконкретнее, или это так для обучения?

anonymous
()

Например, объявить список из Eq и класть в него любой тип, который является инстансом Eq

{-# LANGUAGE GADTs, RankNTypes #-}
data EqWrapper where EqWrap :: Eq a => a -> EqWrapper
consEq :: Eq a => a -> [EqWrapper] -> [EqWrapper]
consEq x xs = EqWrap x : xs
deConsEq :: (forall a. Eq a => a -> b) -> [EqWrapper] -> Maybe (b, [EqWrapper])
deConsEq _ [] = Nothing
deConsEq h (e:es) = Just (h e, es)
Miguel ★★★★★
()
Ответ на: комментарий от anonymous

Это эмуляция самого обычного subtype polymorphism из ООП: кладём набор разнородных объектов в коллецию, лишь бы они имели определённый интерфейс, далее работаем с этими объектами полиморфно, возвращаем назад новую/обновлённую коллекцию.

Но я пока это писал, сам понял, что это динамическая типизация. :) НО! Я думаю h-list здесь подойдёт: я как-то смотрел видео, в котором описывалась его реализация на Scala, так там в принципе всё просто - тип каждой позиции гетерогенного списка определён в типе данного конкретного списка, поэтому когда забираешь N-ый элемент, возвращается объект соответствующего типа, и всё при этом статически типизировано, просто тип списка что-то вроде HList[Int, HList[String]], и он автоматически расширяется/сужается при изменении коллекции.

Bohtvaroh ★★★★
() автор топика
Ответ на: комментарий от Bohtvaroh

Только всё равно придётся для каждого типа определять свой враппер с нужными функциями из type классов...

Bohtvaroh ★★★★
() автор топика
Ответ на: комментарий от Bohtvaroh

Только всё равно придётся для каждого типа определять свой враппер с нужными функциями из type классов...

Можно сделать это единообразно, но только в последнем ghc.

{-# LANGUAGE ConstraintKinds, GADTs, RankNTypes #-}
data Wrapper c where Wrapper :: c a => a -> Wrapper c
cons :: c a => a -> [Wrapper c] -> [Wrapper c]
cons x xs = Wrapper x : xs
deCons :: (forall a. c a => a -> b) -> [Wrapper c] -> Maybe (b, [Wrapper c])
deCons _ [] = Nothing
deCons h (Wrapper x : xs) = Just (h x, xs)

Miguel ★★★★★
()
Ответ на: комментарий от dmfd

Боюсь, это в принципе невозможно. Сдаётся мне, то что вы хотите сделать, требует динамической типизации.

можно Sum type через кучу Either огранизовать, правда это не совсем то, что хочет ТС.

qnikst ★★★★★
()

ОП решает не выдуманную проблему вместо задачи из предметной области? Как это в духе хачкелистов...

anonymous
()
Ответ на: комментарий от Bohtvaroh

Это эмуляция самого обычного subtype

Хаскель в сабтайпинг не умеет и уметь никогда не будет - его система типов слишком слабенькая. То, что вы хотите сделать, в рамках хаскеля - актуальная тема для Ph.D (безо всяких преувеличений, серьезно). Лучше возьмите нормальный, неигрушечный ЯП, и не парьтесь.

anonymous
()
Ответ на: комментарий от Miguel

Для вышеприведённого Wrapper можно написать

instance (c ~ Show) => Show (Wrapper c) where
  show (Wrapper x) = show x

но правильней будет что-то вроде

instance (c <= Show) => Show (Wrapper c) where
  show (Wrapper x) = show x

то есть не эквивалентность как отношения на предикатах, а частичный порядок на них же.

Если появится что-то вроде семейств классов, то можно будет сделать

class family c :<= c'
class instance SomeClass1 :<= Show
class instance SomeClass2 :<= Show
-- ...

instance (c :<= Show) => Show (Wrapper c) where
  show (Wrapper x) = show x

но хочется автоматического порядка на типах (в смысле менее полиморфный тип <= более полиморфный тип и агрегирующий тип <= агрегируемый тип) и классах (в смысле С1 <= C2 для C2 ... => C1 ...) подобно уже существующему (но очень примитивному) отношению эквивалентности ~ на типах и классах. Такое автоматическое отношение <= может сильно усложнить вывод типов.

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

Если появится что-то вроде семейств классов, то можно будет сделать

Да уже можно, причём порядок будет проверяться автоматически:

{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE DefaultSignatures #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE UndecidableInstances #-}
module SubClass where
import GHC.Prim(Constraint)
data Wrapper c where Wrapper :: c a => a -> Wrapper c
cons :: c a => a -> [Wrapper c] -> [Wrapper c]
cons x xs = Wrapper x : xs
deCons :: (forall a. c a => a -> b) -> [Wrapper c] -> Maybe (b, [Wrapper c])
deCons _ [] = Nothing
deCons h (Wrapper x : xs) = Just (h x, xs)
data Void (c :: * -> Constraint) = Void
data Evidence c a where Evidence :: c a => Evidence c a
evidence :: c a => Evidence c a
evidence = Evidence
class c1 :<= c2 where
    isSubClass :: c1 a => Void c1 -> Evidence c2 a
    default isSubClass :: c2 a => Void c1 -> Evidence c2 a
    isSubClass _ = evidence
instance Show :<= Show
instance Floating :<= Fractional
-- instance Fractional :<= Floating -- хрен тебе, а не компиляция
instance (c :<= Show) => Show (Wrapper c) where
    show (Wrapper (a :: t)) = case isSubClass (Void :: Void c) :: Evidence Show t of Evidence -> show a
Увы, без UndecidableInstances я обойтись не сумел.

Miguel ★★★★★
()
Последнее исправление: Miguel (всего исправлений: 2)
Ответ на: комментарий от Miguel

Поправка: функция, не входящая в класс (скажем,

absWrap :: (c :<= Num) => Wrapper c -> Wrapper c
absWrap (Wrapper (a :: t) :: Wrapper c) = case isSubClass (Void :: Void c) :: Evidence Num t of Evidence -> Wrapper (abs a)
) обходится без UndecidableInstances, но требует FlexibleContexts.

Miguel ★★★★★
()
Ответ на: комментарий от Miguel

Не знал что может быть класс от класса, но учитывая что класс (теперь) это (* -> Constraint), то (:<=) :: (* -> Constraint) -> (* -> Constraint) -> Constraint - вполне логично.

Только порядок не вполне проверяется, например

class (Show t, Num t) => ShowNum t
instance (Show t, Num t) => ShowNum t
class ShowNum t => ShowNum2 t
instance ShowNum t => ShowNum2 t

instance ShowNum :<= Show
instance ShowNum2 :<= ShowNum

недостаточно, транзитивности не научить, нужно ещё добавить

instance ShowNum2 :<= Show
quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

Только порядок не вполне проверяется

Я имел в виду, что он проверяется, когда ты пишешь instance. Если ты раскомментируешь третью с конца строчку в моём примере, то компилироваться не будет.

А вот автоматического СОЗДАНИЯ отношения порядка, действительно, нет. Я не знаю, можно ли его сделать; думаю, что нет.

Более забавным, чем класс от класса, мне кажется использование default signature.

Miguel ★★★★★
()
Ответ на: комментарий от Miguel

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

anonymous
()
Ответ на: комментарий от anonymous

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

А в чём проблема-то?

Олег, помнится, сделал для хаскеля объектную систему а-ля окамл, то есть всяко круче жабы.

Miguel ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.