[Haskell] Абстагироваться от контекста в rank-N types
От: nikov США http://www.linkedin.com/in/nikov
Дата: 06.10.09 07:46
Оценка:
Есть такой фрагмент кода:
{-# LANGUAGE RankNTypes, ImpredicativeTypes, ScopedTypeVariables, ExistentialQuantification #-}
 
data Numeric = forall a. Num a => Numeric a

apply :: [forall a. Num a => a -> Integer] -> [Numeric] -> [Integer]
apply = zipWith (\f (Numeric n) -> f n)

composeNum :: [forall b. Num b => b -> d] -> [forall a. Num a => a -> a] -> [forall c. Num c => c -> d]
composeNum = zipWith (\f (g :: forall a. Num a => a -> a) -> f.g)

composeEnum :: [forall b. Enum b => b -> d] -> [forall a. Enum a => a -> a] -> [forall c. Enum c => c -> d]
composeEnum = zipWith (\f (g :: forall a. Enum a => a -> a) -> f.g)


1. Можно ли как-то абстрагироваться от контекста (Num a) и избежать дублирования кода в похожих методах composeNum и composeEnum? Можно ли как-то сделать контекст параметром?
2. Можно ли избежать явного указания типа параметра g в лямбда-выражении?
Re: [Haskell] Абстагироваться от контекста в rank-N types
От: thesz Россия http://thesz.livejournal.com
Дата: 06.10.09 09:30
Оценка: 30 (1)
Здравствуйте, nikov, Вы писали:

N>Есть такой фрагмент кода:

N>
N>{-# LANGUAGE RankNTypes, ImpredicativeTypes, ScopedTypeVariables, ExistentialQuantification #-}
 
N>data Numeric = forall a. Num a => Numeric a

N>apply :: [forall a. Num a => a -> Integer] -> [Numeric] -> [Integer]
N>apply = zipWith (\f (Numeric n) -> f n)

N>composeNum :: [forall b. Num b => b -> d] -> [forall a. Num a => a -> a] -> [forall c. Num c => c -> d]
N>composeNum = zipWith (\f (g :: forall a. Num a => a -> a) -> f.g)

N>composeEnum :: [forall b. Enum b => b -> d] -> [forall a. Enum a => a -> a] -> [forall c. Enum c => c -> d]
N>composeEnum = zipWith (\f (g :: forall a. Enum a => a -> a) -> f.g)
N>


N>1. Можно ли как-то абстрагироваться от контекста (Num a) и избежать дублирования кода в похожих методах composeNum и composeEnum?


Нет.

N>Можно ли как-то сделать контекст параметром?


Нет.

N>2. Можно ли избежать явного указания типа параметра g в лямбда-выражении?


-- {-# LANGUAGE , ExistentialQuantification #-}
{-# LANGUAGE GADTs, RankNTypes, ScopedTypeVariables, ImpredicativeTypes #-}
 
data Numeric where Numeric :: Num a => a -> Numeric

apply :: [forall a. Num a => a -> Integer] -> [Numeric] -> [Integer]
apply = zipWith (\f (Numeric n) -> f n)

composeNum :: [forall b. Num b => b -> d] -> [forall a. Num a => a -> a] -> [forall c. Num c => c -> d]
composeNum = zipWith (\f (g) -> f.g)

composeEnum :: [forall b. Enum b => b -> d] -> [forall a. Enum a => a -> a] -> [forall c. Enum c => c -> d]
composeEnum = zipWith (\f (g) -> f.g)


ghc 6.10.1

А зачем тебе такой вычурный код?
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[2]: [Haskell] Абстагироваться от контекста в rank-N types
От: nikov США http://www.linkedin.com/in/nikov
Дата: 06.10.09 10:10
Оценка:
Здравствуйте, thesz, Вы писали:

N>>2. Можно ли избежать явного указания типа параметра g в лямбда-выражении?


T>
T>composeEnum :: [forall b. Enum b => b -> d] -> [forall a. Enum a => a -> a] -> [forall c. Enum c => c -> d]
T>composeEnum = zipWith (\f (g) -> f.g)
T>


Ой, точно. Почему-то этот вариант не попробовал, а просто zipWith (.) не сработал.

T>А зачем тебе такой вычурный код?


Сравниваю возможности Scala и Haskell.
Re[3]: [Haskell] Абстагироваться от контекста в rank-N types
От: thesz Россия http://thesz.livejournal.com
Дата: 06.10.09 10:53
Оценка:
Здравствуйте, nikov, Вы писали:

N>Здравствуйте, thesz, Вы писали:


T>>А зачем тебе такой вычурный код?


N>Сравниваю возможности Scala и Haskell.


Смысл-то в коде какой?

Ведь похожее можно сделать попроще.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[4]: [Haskell] Абстагироваться от контекста в rank-N types
От: nikov США http://www.linkedin.com/in/nikov
Дата: 06.10.09 11:23
Оценка:
Здравствуйте, thesz, Вы писали:

T>Смысл-то в коде какой?


Есть гетерогенный список объектов, реализующий какой-то общий интерфейс. В ООП такие объекты обычно хранятся просто приведенными к базовому абстрактному типу. В Haskell, как написано в тьюториалах, такое делается с помощью экзистенциальных типов и type box. В качестве иллюстрации у меня все объекты в списке реализуют классом типов Num. С этим гетерогенным списком мы умеем что-то делать. Например, у нас есть список функций, и мы можем сшить (zip) эти два списка, применив каждую функцию к соответствующему аргументу. Так как аргументы могут быть разных типов, то функции в списке хранятся полиморфные, умеющие применяться к любому типу, реализующему данный класс. Теперь, допустим у нас есть два таких списка функций и мы хотим получить их поэлементную композицию. Мы пишем функцию compose, но в ее типе жестко зашит класс типов, которым объединены элементы гетерогенного списка (в моем случае Num). Хотя сама функция compose этим классом никак не пользуется. И если нам вдруг придется решать такую же задачу для другого класса типов, но нам придется слово-в-слово продублировать декларацию функции compose, лишь заменив в ее типе Num, скажем на Enum. Налицо дублирование кода. Отсюда возникает желание от этого контекста абстрагироваться. Скажем, в Scala, нет отдельной сущности "класс типа". Их роль выполняют те же саме трейты, которые могут быть вынесены из метода или типа в качестве параметра.
Re[5]: [Haskell] Абстагироваться от контекста в rank-N types
От: thesz Россия http://thesz.livejournal.com
Дата: 06.10.09 12:25
Оценка:
Здравствуйте, nikov, Вы писали:

N>Здравствуйте, thesz, Вы писали:


T>>Смысл-то в коде какой?


N>Есть гетерогенный список объектов, реализующий какой-то общий интерфейс.


И я не понимаю, зачем это нужно. Это попытка натянуть решение из Скалы (ООП) на Хаскель.

Ну, и ладно.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[6]: [Haskell] Абстагироваться от контекста в rank-N types
От: nikov США http://www.linkedin.com/in/nikov
Дата: 06.10.09 12:36
Оценка:
Здравствуйте, thesz, Вы писали:

N>>Есть гетерогенный список объектов, реализующий какой-то общий интерфейс.


T>И я не понимаю, зачем это нужно. Это попытка натянуть решение из Скалы (ООП) на Хаскель.


На мой взгляд, в Haskell Wiki для этого случая приводится вполне жизненная ситуация.
Re: [Haskell] Абстагироваться от контекста в rank-N types
От: palm mute  
Дата: 06.10.09 13:02
Оценка:
Здравствуйте, nikov, Вы писали:

N>1. Можно ли как-то абстрагироваться от контекста (Num a) и избежать дублирования кода в похожих методах composeNum и composeEnum? Можно ли как-то сделать контекст параметром?


С помощью трюка, описанного в документации GHC (надо искать фразу "one possible application is to reify dictionaries"), у меня получилось следующее:
{-# LANGUAGE RankNTypes, ImpredicativeTypes, ScopedTypeVariables, GADTs #-}
 
data NumInst a where
     MkNumInst :: Num a => NumInst a

composeList :: [forall b. ctx b -> b -> d] -> [forall a. ctx a -> a -> a] -> [forall c. ctx c -> c -> d]
composeList = zipWith (\f g ctx -> f ctx . g ctx)

test = (incAndShow (41 :: Int), incAndShow (41 :: Double))
    where 
      incAndShow :: Num a => a -> String
      incAndShow = f MkNumInst
          where f = head (composeList [showNum] [incNum])

      showNum :: NumInst a -> a -> String
      showNum MkNumInst = show

      incNum :: NumInst a -> a -> a
      incNum MkNumInst = (+1)
Re[7]: [Haskell] Абстагироваться от контекста в rank-N types
От: thesz Россия http://thesz.livejournal.com
Дата: 06.10.09 13:23
Оценка:
Здравствуйте, nikov, Вы писали:

N>Здравствуйте, thesz, Вы писали:


N>>>Есть гетерогенный список объектов, реализующий какой-то общий интерфейс.


T>>И я не понимаю, зачем это нужно. Это попытка натянуть решение из Скалы (ООП) на Хаскель.


N>На мой взгляд, в Haskell Wiki для этого случая приводится вполне жизненная ситуация.


Не-а. Не жизненная. Выглядит такой, но жизни не имеет.

Тем не менее. там приводится вполне Хаскельное решение на обобщённых алгебраических типах данных.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re: [Haskell] Абстагироваться от контекста в rank-N types
От: MigMit Россия http://migmit.vox.com
Дата: 06.10.09 18:02
Оценка:
N>1. Можно ли как-то абстрагироваться от контекста (Num a) и избежать дублирования кода в похожих методах composeNum и composeEnum? Можно ли как-то сделать контекст параметром?

Да. Как всегда — явно передавая словарь. Можно сделать финт ушами:
data NumD a = NumD {numD :: forall p. (forall x. Num x => p x) -> p a}
defaultNum :: Num a => NumD a
defaultNum = NumD id

data EnumD a = EnumD {enumD :: forall p. (forall x. Enum x => p x) -> p a}
defaultEnum :: Enum a => EnumD a
defaultEnum = EnumD id

После чего писать что-то типа
data Some q = forall a. Some (q a) a
type Numeric' = Some NumD
apply' :: [forall a. q a -> a -> Integer] -> [Some q] -> [Integer]
apply' = zipWith (\f (Some qa a) -> f qa a)
composeQ :: [forall b. q b -> b -> d] -> [forall a. q a -> a -> a] -> [forall c. q c -> c -> d]
composeQ = zipWith (\f g qc -> f qc . g qc)


N>2. Можно ли избежать явного указания типа параметра g в лямбда-выражении?


Ну, собственно, код выше как бы намекает, что можно.
Re[8]: [Haskell] Абстагироваться от контекста в rank-N types
От: Alxndr Германия http://www.google.com/profiles/alexander.poluektov#buzz
Дата: 08.10.09 15:26
Оценка:
Здравствуйте, thesz, Вы писали:

N>>На мой взгляд, в Haskell Wiki для этого случая приводится вполне жизненная ситуация.


T>Не-а. Не жизненная. Выглядит такой, но жизни не имеет.


А что с ней не так?
Re[9]: [Haskell] Абстагироваться от контекста в rank-N types
От: thesz Россия http://thesz.livejournal.com
Дата: 08.10.09 15:37
Оценка:
Здравствуйте, Alxndr, Вы писали:

A>Здравствуйте, thesz, Вы писали:


N>>>На мой взгляд, в Haskell Wiki для этого случая приводится вполне жизненная ситуация.

T>>Не-а. Не жизненная. Выглядит такой, но жизни не имеет.
A>А что с ней не так?

Конкретное представление лучше практически со всех сторон.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[10]: [Haskell] Абстагироваться от контекста в rank-N type
От: Alxndr Германия http://www.google.com/profiles/alexander.poluektov#buzz
Дата: 08.10.09 15:54
Оценка:
Здравствуйте, thesz, Вы писали:

T>Конкретное представление лучше практически со всех сторон.


Как в Haskell принято решать задачи, являющиеся классическими иллюстрациями ОО-дизайна?
Скажем, есть игра. Различные монстры с различным ИИ. На каждой итерации игрового цикла каждый монстр должен сделать нечто, что он считает самым правильным исходя из ситуации.
Т.е. там, где в C++ написали бы

struct Monster
{
  virtual void act(Context) = 0;
};

vector<Monster*> monsters;
Context context;

int main()
{
  for_all(monsters, &Monster::act, context);
}

struct Goblin : Monster { ... }
struct Boss : Monster { ... }
// дизайнеры постоянно выдумывают новых монстров


Как правильно подойти к решению задачи "функционально"?
Re[11]: [Haskell] Абстагироваться от контекста в rank-N type
От: thesz Россия http://thesz.livejournal.com
Дата: 08.10.09 16:11
Оценка:
Здравствуйте, Alxndr, Вы писали:

A>Здравствуйте, thesz, Вы писали:


T>>Конкретное представление лучше практически со всех сторон.


A>Как в Haskell принято решать задачи, являющиеся классическими иллюстрациями ОО-дизайна?


Не решая их в ОО стиле.

A>Скажем, есть игра. Различные монстры с различным ИИ. На каждой итерации игрового цикла каждый монстр должен сделать нечто, что он считает самым правильным исходя из ситуации.

A>Т.е. там, где в C++ написали бы

A>
A>struct Monster
A>{
A>  virtual void act(Context) = 0;
A>};

A>vector<Monster*> monsters;
A>Context context;

A>int main()
A>{
A>  for_all(monsters, &Monster::act, context);
A>}

A>struct Goblin : Monster { ... }
A>struct Boss : Monster { ... }
A>// дизайнеры постоянно выдумывают новых монстров
A>


A>Как правильно подойти к решению задачи "функционально"?


Обобщаем требования монстров, делаем структуру, описывающую их поведение, интерпретируем.

Либо так, как выше.

class Monster a where
    act :: Context -> a -> IO a

data Boss = ...
data Goblin = ...

instance Monster Boss where
    act cxt (Boss ...) = ...
instance Monster Goblin where
    act cxt (Goblin ...) = ...

monsters = [...]
main = mapM (act cxt) monsters


Требование "дизайнеры постоянно придумывают" — не бывает. Поэтому всегда можно обобщить структуру поведения персонажей и получить конечное дерево решений.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[12]: [Haskell] Абстагироваться от контекста в rank-N type
От: Alxndr Германия http://www.google.com/profiles/alexander.poluektov#buzz
Дата: 08.10.09 16:27
Оценка:
Здравствуйте, thesz, Вы писали:

A>>Как правильно подойти к решению задачи "функционально"?


T>Обобщаем требования монстров, делаем структуру, описывающую их поведение, интерпретируем.


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

T>
T>class Monster a where
T>    act :: Context -> a -> IO a

T>data Boss = ...
T>data Goblin = ...

T>instance Monster Boss where
T>    act cxt (Boss ...) = ...
T>instance Monster Goblin where
T>    act cxt (Goblin ...) = ...

T>monsters = [...]
T>main = mapM (act cxt) monsters
T>


T>Требование "дизайнеры постоянно придумывают" — не бывает. Поэтому всегда можно обобщить структуру поведения персонажей и получить конечное дерево решений.


Посылка ложная, к сожалению. Поэтому "поэтому" может быть истинно, а может быть и нет.
Re[12]: [Haskell] Абстагироваться от контекста в rank-N type
От: Alxndr Германия http://www.google.com/profiles/alexander.poluektov#buzz
Дата: 08.10.09 16:45
Оценка:
Здравствуйте, thesz, Вы писали:

T>Либо так, как выше.


T>
T>class Monster a where
T>    act :: Context -> a -> IO a

T>data Boss = ...
T>data Goblin = ...

T>instance Monster Boss where
T>    act cxt (Boss ...) = ...
T>instance Monster Goblin where
T>    act cxt (Goblin ...) = ...

T>monsters = [...]
T>main = mapM (act cxt) monsters
T>


Я так понимаю, это не работает.
Ведь Boss и Goblin в данном случае — разные типы, а значит, их нельзя положить в список (возвращаемый monsters)?
Re[13]: [Haskell] Абстагироваться от контекста в rank-N type
От: thesz Россия http://thesz.livejournal.com
Дата: 08.10.09 16:51
Оценка: 4 (1)
Здравствуйте, Alxndr, Вы писали:

A>Здравствуйте, thesz, Вы писали:


A>>>Как правильно подойти к решению задачи "функционально"?


T>>Обобщаем требования монстров, делаем структуру, описывающую их поведение, интерпретируем.

A>Можешь пояснить на примере гоблинов, боссов и еще-не-придуманных-монстров?
A>Только без мантры "не бывает".

Самое простое.

Монстр может производить с внешним миром ограниченное количество действий, это выходной алфавит. Монстр может получать от внешнего мира ограниченное количество данных, это входной алфавит.

Итак, мы можем свести описание монстра к программе, что распознаёт язык входных воздействий на основе некоей грамматики и порождает предложение для внешнего мира.

Самое приятное в том, что мы статически можем проверить некоторые свойства мира — например, кто (не) понимает такие-то сообщения от таких-то персонажей.

Вот, примерно, так. Была ОО задача, стала задача на разбор языков и трансляцию.

T>>
T>>main = mapM (act cxt) monsters
T>>


T>>Требование "дизайнеры постоянно придумывают" — не бывает. Поэтому всегда можно обобщить структуру поведения персонажей и получить конечное дерево решений.

A>Посылка ложная, к сожалению. Поэтому "поэтому" может быть истинно, а может быть и нет.

Лично я не вижу, как можно придумать нового монстра, если описаны несколько классов старых. Если у нас есть монстры с одной, двумя и тремя ногами, то сделать четырёхногого проще простого.

Дело в том, что игровая механика достаточно строго ограничена законами мира и передаваемой историей мира игры. Поэтому появление ещё одного класса монстров надо тщательно легендировать. Что затратно для дизайнеров.

Им проще уложить "нового" монстра в рамки старых.

Наш ответственный за анимацию моделей в игре как-то рассказал, что большинство трехногих моделей делается из 4-хногих. Просто потому, что такая поддержка есть в 3D Max и проще склеить персонажу две ноги, чем делать что-то своё.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[13]: [Haskell] Абстагироваться от контекста в rank-N type
От: thesz Россия http://thesz.livejournal.com
Дата: 08.10.09 17:03
Оценка:
Здравствуйте, Alxndr, Вы писали:

A>Здравствуйте, thesz, Вы писали:


T>>Либо так, как выше.


T>>
T>>class Monster a where
T>>    act :: Context -> a -> IO a

T>>data Boss = ...
T>>data Goblin = ...

T>>instance Monster Boss where
T>>    act cxt (Boss ...) = ...
T>>instance Monster Goblin where
T>>    act cxt (Goblin ...) = ...

T>>monsters = [...]
T>>main = mapM (act cxt) monsters
T>>


A>Я так понимаю, это не работает.

A>Ведь Boss и Goblin в данном случае — разные типы, а значит, их нельзя положить в список (возвращаемый monsters)?

data GMonster where
    GMonster :: Monster a => a -> GMonster

instance Monster GMonster where
    act cxt (GMonster a) = liftM GMonster $ act cxt a

monsters :: [GMonster]


Делов-то.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[14]: [Haskell] Абстагироваться от контекста в rank-N type
От: Alxndr Германия http://www.google.com/profiles/alexander.poluektov#buzz
Дата: 08.10.09 17:19
Оценка:
Здравствуйте, thesz, Вы писали:

T>Вот, примерно, так. Была ОО задача, стала задача на разбор языков и трансляцию.


Спасибо!

T>>>Требование "дизайнеры постоянно придумывают" — не бывает. Поэтому всегда можно обобщить структуру поведения персонажей и получить конечное дерево решений.


A>>Посылка ложная, к сожалению. Поэтому "поэтому" может быть истинно, а может быть и нет.


T>Дело в том, что игровая механика достаточно строго ограничена законами мира и передаваемой историей мира игры. Поэтому появление ещё одного класса монстров надо тщательно легендировать. Что затратно для дизайнеров.


T>Им проще уложить "нового" монстра в рамки старых.


Это всё немного искусственные ограничения, ну да ладно — не будем играть в "нет, ну а если все-таки".

Рассмотрим реальный пример.
Есть вьюер. Он умеет рисовать точки, линии, полигоны — разными цветами, толщиной, со стрелочками и без, и т.п. А также картинки и текст. У него для этого есть API.
Есть пользовательские данные: файлы в самых разнообразных форматах, содержащих обычно геодезическую информацию (тоже самую разнообразную: здания, дороги, элементы ландшафта и т.п.)
Вьюер и его разработчик не знают ни всех существующих форматов данных, ни всех существующих сущностей — многие просто по определению появляются позже.
Мы решаем эту проблему реализуя систему плагинов, которые работают с вьюером.

Решают же на Хаскеле такие задачи? Как?
Re[11]: [Haskell] Абстагироваться от контекста в rank-N type
От: MigMit Россия http://migmit.vox.com
Дата: 08.10.09 17:34
Оценка: 4 (1)
Здравствуйте, Alxndr, Вы писали:

A>Т.е. там, где в C++ написали бы


A>
A>struct Monster
A>{
A>  virtual void act(Context) = 0;
A>};

A>vector<Monster*> monsters;
A>Context context;

A>int main()
A>{
A>  for_all(monsters, &Monster::act, context);
A>}

A>struct Goblin : Monster { ... }
A>struct Boss : Monster { ... }
A>// дизайнеры постоянно выдумывают новых монстров
A>

newtype Monster = Monster {act :: Context -> IO ()}
monsters :: [Monster]
data GoblinParameters = ...whatever...
goblin :: GoblinParameters -> Monster
goblin (...) = Monster $ \context -> ...

Один из вариантов.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.