[Haskell] Абстагироваться от контекста в rank-N types - Декларативное программирование

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

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

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

A>Решают же на Хаскеле такие задачи? Как?

Плагинами.

Почему бы и нет?

Здравствуйте, 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

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

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

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

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

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

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

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

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

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

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

T>>

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

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

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

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

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

Наш ответственный за анимацию моделей в игре как-то рассказал, что большинство трехногих моделей делается из 4-хногих. Просто потому, что такая поддержка есть в 3D Max и проще склеить персонажу две ноги, чем делать что-то своё.

Здравствуйте, 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 -> ...

Один из вариантов.

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

{-# 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 в лямбда-выражении?

Здравствуйте, 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.

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

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

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

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

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

Ведь похожее можно сделать попроще.

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

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

Есть гетерогенный список объектов, реализующий какой-то общий интерфейс. В ООП такие объекты обычно хранятся просто приведенными к базовому абстрактному типу. В Haskell, как написано в тьюториалах, такое делается с помощью экзистенциальных типов и type box. В качестве иллюстрации у меня все объекты в списке реализуют классом типов Num. С этим гетерогенным списком мы умеем что-то делать. Например, у нас есть список функций, и мы можем сшить (zip) эти два списка, применив каждую функцию к соответствующему аргументу. Так как аргументы могут быть разных типов, то функции в списке хранятся полиморфные, умеющие применяться к любому типу, реализующему данный класс. Теперь, допустим у нас есть два таких списка функций и мы хотим получить их поэлементную композицию. Мы пишем функцию compose, но в ее типе жестко зашит класс типов, которым объединены элементы гетерогенного списка (в моем случае Num). Хотя сама функция compose этим классом никак не пользуется. И если нам вдруг придется решать такую же задачу для другого класса типов, но нам придется слово-в-слово продублировать декларацию функции compose, лишь заменив в ее типе Num, скажем на Enum. Налицо дублирование кода. Отсюда возникает желание от этого контекста абстрагироваться. Скажем, в Scala, нет отдельной сущности "класс типа". Их роль выполняют те же саме трейты, которые могут быть вынесены из метода или типа в качестве параметра.

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

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

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

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

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

Ну, и ладно.

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

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

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

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

Здравствуйте, 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)

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

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

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

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

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

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

Тем не менее. там приводится вполне Хаскельное решение на обобщённых алгебраических типах данных.

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 в лямбда-выражении?

Ну, собственно, код выше как бы намекает, что можно.

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

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

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

А что с ней не так?

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

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

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

A>А что с ней не так?

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

Здравствуйте, 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 { ... }
// дизайнеры постоянно выдумывают новых монстров

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

Здравствуйте, 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

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

Здравствуйте, 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>Требование "дизайнеры постоянно придумывают" — не бывает. Поэтому всегда можно обобщить структуру поведения персонажей и получить конечное дерево решений.

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

Здравствуйте, 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)?

Здравствуйте, 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]

Делов-то.

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

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

Спасибо!

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

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

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

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

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

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

Решают же на Хаскеле такие задачи? Как?

От:	thesz	http://thesz.livejournal.com
Дата:	08.10.09 17:53
Оценка:	4 (1)

От:	thesz	http://thesz.livejournal.com
Дата:	06.10.09 09:30
Оценка:	30 (1)

От:	thesz	http://thesz.livejournal.com
Дата:	08.10.09 16:51
Оценка:	4 (1)

От:	MigMit	http://migmit.vox.com
Дата:	08.10.09 17:34
Оценка:	4 (1)

От:	nikov	http://www.linkedin.com/in/nikov
Дата:	06.10.09 07:46
Оценка:

От:	Alxndr	http://www.google.com/profiles/alexander.poluektov#buzz
Дата:	08.10.09 15:26
Оценка: