Как вы управляете графом объектов в Haskell?

Я пытаюсь переучивать системный анализ. У меня много объектно-ориентированного мышления, для которого я пока не могу найти эквиваленты в Haskell.

Вымышленная система состоит из станций скорой помощи, скорой помощи и экипажа. (Он уже получает объект-y.) Все это состояние можно обернуть в большой тип SystemState. SystemState [Станции] [Машины скорой помощи] [Экипаж]. Затем я могу создавать функции, которые принимают SystemState, и возвращать новый SystemState.

module AmbSys
    ( version
    , SystemState
    , Station
    , Ambulance
    , Crew
    ) where

version = "0.0.1"

data SystemState = SystemState [Station] [Ambulance] [Crew] deriving (Show)

data Station = Station { stName :: String
                       , stAmbulances :: [Ambulance]
                       } deriving (Show)

data Ambulance = Ambulance { amCallSign :: String
                           , amStation :: Station
                           , amCrew :: [Crew]
                           } deriving (Show)

data Crew = Crew { crName :: String
                 , crAmbulance :: Ambulance
                 , crOnDuty :: Bool
                 } deriving (Show)

Здесь сеанс ghci, где я создаю некоторые данные.

*AmbSys> :load AmbSys                 
[1 of 1] Compiling AmbSys           ( AmbSys.hs, interpreted )
Ok, modules loaded: AmbSys.
*AmbSys> let s = Station "London" []                
*AmbSys> let a = Ambulance "ABC" s []               
*AmbSys> let s' = Station "London" [a]
*AmbSys> let c = Crew "John Smith" a False        
*AmbSys> let a' = Ambulance "ABC" s [c]   
*AmbSys> let s'' = Station "London" [a']             
*AmbSys> let system_state = SystemState [s''] [a'] [c]
*AmbSys> system_state                                 
SystemState [Station {stName = "London", stAmbulances = [Ambulance {amCallSign = "ABC",
 amStation = Station {stName = "London", stAmbulances = []}, amCrew = [Crew 
 {crName = "John Smith", crAmbulance = Ambulance {amCallSign = "ABC", 
 amStation = Station {stName = "London", stAmbulances = []}, amCrew = []}, 
 crOnDuty = False}]}]}] [Ambulance {amCallSign = "ABC", amStation = Station {
 stName = "London", stAmbulances = []}, amCrew = [Crew {crName = "John Smith",
 crAmbulance = Ambulance {amCallSign = "ABC", amStation = Station {stName = "London",
 stAmbulances = []}, amCrew = []}, crOnDuty = False}]}] [Crew {crName = "John Smith",
 crAmbulance = Ambulance {amCallSign = "ABC", amStation = Station {stName = "London",
 stAmbulances = []}, amCrew = []}, crOnDuty = False}]

Здесь вы можете увидеть несколько проблем:

  • Я не смог создать согласованный SystemState - некоторые из значений являются "старыми" значениями, такими как s или s ', а не s' '.
  • много ссылок на "те же" данные имеют отдельные копии.

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

Моя проблема в том, что я должен найти и изменить члена экипажа в скорой помощи и (идентичной копии) члена экипажа в SystemState.

Это возможно для небольших систем, но реальные системы имеют гораздо больше связей. Это похоже на проблему n-квадрата.

Я прекрасно понимаю, что я думаю о системе объектно-ориентированным образом.

Как бы такая система была правильно создана в Haskell?

Редактировать: Спасибо всем за ваши ответы, а также тем, кто на reddit тоже http://www.reddit.com/r/haskell/comments/b87sc/how_do_you_manage_an_object_graph_in_haskell/

Теперь я понимаю, что могу делать то, что хочу в Haskell. С другой стороны, похоже, что диаграммы объектов/записей/структур не являются объектами "первого класса" в Haskell (как и в C/Java/и т.д.) Из-за необходимого отсутствия ссылок. Там просто компромисс - некоторые задачи синтаксически проще в Haskell, некоторые из них более простые (и более небезопасные) в C.

Ответы

Ответ 1

Небольшой совет: если вы используете рекурсивный let или where (в файле .hs, я не думаю, что он работает в ghci), вы можете, по крайней мере, настроить начальный график более легко следующим образом:

ambSys = SystemState [s] [a] [c] where
    s = Station "London" [a]
    a = Ambulance "ABC" s [c]
    c = Crew "John Smith" a False

Это приведет вас к состоянию, которое, как я думаю, вы пытаетесь достичь, но не пытайтесь использовать производные экземпляры Show:-) Обновление состояний, подобных этим, - это еще одна возможность beans; Я расскажу, что подумал и посмотрю, что я придумал.

EDIT: я подумал об этом еще немного, и вот что я бы сделал:

Я бы разбил циклы в графе объектов с помощью клавиш. Что-то вроде этого будет работать (я использовал подобный подход при построении реальных графиков):

import qualified Data.Map as M

version = "0.0.1"

newtype StationKey = StationKey String deriving (Eq,Ord,Show)
newtype AmbulanceKey = AmbulanceKey String deriving (Eq,Ord,Show)
newtype CrewKey = CrewKey String deriving (Eq,Ord,Show)

data SystemState = SystemState (M.Map StationKey Station) (M.Map AmbulanceKey Ambulance) (M.Map CrewKey Crew) deriving (Show)

data Station = Station { stName :: StationKey
                       , stAmbulances :: [AmbulanceKey]
                       } deriving (Show)

data Ambulance = Ambulance { amCallSign :: AmbulanceKey
                           , amStation :: StationKey
                           , amCrew :: [CrewKey]
                           } deriving (Show)

data Crew = Crew { crName :: CrewKey
                 , crAmbulance :: AmbulanceKey
                 , crOnDuty :: Bool
                 } deriving (Show)

ambSys = SystemState (M.fromList [(londonKey, london)]) (M.fromList [(abcKey, abc)]) (M.fromList [(johnSmithKey, johnSmith)]) where
    londonKey = StationKey "London"
    london = Station londonKey [abcKey]
    abcKey = AmbulanceKey "ABC"
    abc = Ambulance abcKey londonKey [johnSmithKey]
    johnSmithKey = CrewKey "John Smith"
    johnSmith = Crew johnSmithKey abcKey False

И тогда вы можете начать определять свои собственные модификаторы, изменяющие состояние. Как вы можете видеть, теперь здание состояний более многословно, но Show ing снова работает снова!

Кроме того, я бы, вероятно, установил тип класса, чтобы сделать ссылку между Station и StationKey итерами более явными, если это становится слишком громоздким. Я не делал этого в моем графическом коде, так как там у меня было только два ключевых типа, которые также были разными, поэтому новые типы не нужны.

Ответ 2

Он не получает Object-Oriented-y, пока не начнет говорить о наследовании и полиморфизме подтипов. Программы содержали структуры данных, называемые "скорая помощь" и "станция" задолго до того, как ОО было задумано; OO не имеет монополии на абстрагирование и инкапсуляцию данных. Конструкция FP также будет "управляемой доменом", как это потребует программирования.

Проблема, с которой вы сталкиваетесь, заключается в том, как управлять состоянием, и это хроническая проблема в Haskell (фактически, в любой системе программирования, см. раздел 3.1.3 SICP (структура Абельсона и Суссмана и интерпретация компьютерных программ http://mitpress.mit.edu/sicp/ (Не отвлекайтесь на большие академические слова или доменное имя, это очень читаемо - их пример - банковский счет).

Ваша проблема в том, что ур ссылается и держится на старом, устаревшем состоянии. Я предлагаю вам писать функции, которые принимают текущее состояние, изменяют его и возвращают новое состояние. Что-то вроде:

addStation state station = 
     let (SystemState stations ambs crews) = state
     in SystemState (station:stations) ambs crews)

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

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

Ответ 3

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

Конечно, существует более прямое кодирование, использующее ссылки, которые ведут себя скорее как то, к чему вы привыкли:

data Station = Station { stName :: String 
                       , stAmbulances :: [IORef Ambulance] 
                       } deriving (Show) 

data Ambulance = Ambulance { amCallSign :: String 
                           , amStation :: IORef Station 
                           , amCrew :: [IORef Crew] 
                           } deriving (Show) 

data Crew = Crew { crName :: String 
                 , crAmbulance :: IORef Ambulance 
                 , crOnDuty :: Bool 
                 } deriving (Show) 

Это приводит к значительному боковому эффекту программирования. По сути, вы просто начинаете писать C/С++ в Haskell, используя монаду IO.

Для решения этой проблемы существуют два подхода, подобные Haskell.

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

Другой - убить круговые ссылки:

data Station = Station { stName :: String 
                       , stAmbulances :: [Ambulance] 
                       } deriving (Show) 

data Ambulance = Ambulance { amCallSign :: String 
                           , amCrew :: [Crew] 
                           } deriving (Show) 

data Crew = Crew { crName :: String 
                 , crOnDuty :: Bool 
                 } deriving (Show) 

Вы можете получить доступ к экипажу со станции:

stCrew :: Station -> [Crew]
stCrew = stAmbulances >>= amCrew

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

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

import Control.Monad ((>=>))
import Data.Map (Map)
import qualified Data.Map as Map

type Name = String
newtype CrewTraits = CrewTraits { onDuty :: Bool }
type Crew = (Name, CrewTraits) 

type CallSign = String
type AmbulanceTraits = Map Name AssignmentTraits
type Amulance = (CallSign, AmbulanceTraits)

type StationName = String
type StationTraits = Map CallSign AmbulanceTraits
type Station = (StationName,StationTraits)

type Fleet = Map StationName StationTraits

crew :: Name -> Bool -> Crew
crew name isOnDuty = (name, CrewTraits isOnDuty)

ambulance :: CallSign -> [Crew] -> Ambulance
ambulance sign crew = (sign, Map.fromList crew)

station :: StationName -> [Ambulance] -> Station
station name ambulances = (name, Map.fromList ambulances)

fleet :: [Station] -> Fleet
fleet = Map.fromList

Теперь вы можете изменить станцию ​​только с помощью встроенных функций из Data.Map:

updateStationTraits :: (StationName -> StationTraits -> Maybe StationTraits) ->
                       StationName -> Fleet -> Fleet
updateStationTraits = Map.updateWithKey

которые вы могли бы сделать, выглядят немного более естественными, повторяя Name и StationTraits:

updateStation :: (Station -> Maybe StationTraits) -> 
                 StationName -> Fleet -> Fleet
updateStation = Map.updateWithKey . curry

addAmbulanceToFleet :: Ambulance -> StationName -> Fleet -> Fleet
addAmbulanceToFleet (k,v) = Map.adjust (Map.insert k v)

Со всем этим теперь вы можете объединить понятие пути в этой структуре с более ранним понятием ключа:

type CrewPath = (StationName,CallSign,Name)
type AmbulancePath = (StationName, CallSign)
type StationPath = StationName

lookupCrewTraits :: CrewKey -> Fleet -> Maybe CrewTraits
lookupCrewTraits (s,c,n) = lookup s >=> lookup c >=> lookup n

lookupCrew :: CrewKey -> Fleet -> Maybe Crew
lookupCrew [email protected](_,_,n) = (,) n `fmap` lookupCrewTraits scn

Ответ 4

Haskell - отличный выбор для моделирования системы, которую вы описываете.

Однако, как и на любом языке программирования, способ моделирования вашей системы в значительной степени зависит от того, какие операции вы хотите сделать на нем. И функциональный язык программирования, такой как Haskell, поможет вам сосредоточиться на этом. Моделирование данных приятно, но где функции?

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

Но основная проблема здесь заключается в том, как эффективно использовать GHCi.

Что именно вы пытаетесь сделать в GHCi? Я провожу много времени на Запрос GHCi. Я могу разделить это время на три категории: изучение функций лучше понимать их, тестировать и отлаживать функции, чтобы убедиться, что они работают, и выполнение разовых вычислений с использованием функций, которые я уже понимаю и уже знают, что работают. Я не думаю, что использовал GHCi для просто набрав структуры данных и имея GHCi, выплюнул их обратно.

Тем не менее, для каждого из этих трех применений мне нужны структуры данных. Обычно те, которые мне нужны, достаточно просты, и я могу введите всю вещь за один раз. Они фактически не должны быть очень простыми для что - не забывайте, что вы можете набрать несколько взаимно-рекурсивных определения в одном выражении let, разделив их на ';' и что GHCi поддерживает многострочные операторы с командами ": {" и ":}".

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

Чтобы получить изменяемую переменную, которую вы повторно изменяете для сборки по своему составу, аналогично тому, как вы это сделаете в командная строка запрашивает императивный язык, посмотрите на модуль Data.IORef. Если вы новичок в Haskell, я бы рекомендуем избегать Data.IORef, как чума в вашем программировании - это всегда соблазняет вас, и это почти всегда неправильно делать. Но в подсказке GHCi это прекрасно.

Честно говоря, я почти никогда этого не делаю. Будучи ленивым, я просто использую стрелка вверх и другие клавиши редактирования командной строки, чтобы получить все это в одну команду GHCi пошагово.

И, конечно, если структура данных, которую вы вводите, на самом деле значимый, а не примерный, вы хотите ввести это в файл в вашем любимом редакторе Haskell, а не в в подсказке. Затем вы будете использовать интеграцию с вашим редактором GHCi, или GHCi ": r", чтобы сохранить обновленную версию вашего структура, доступная в GHCi.

Ответ 5

Существует несколько способов. Один простой способ - представить свои данные как базу данных SQL. То есть ваши станции, машины скорой помощи и экипаж - это все таблицы со спутниковыми данными, связанными с ними. Другой вариант - определить его как базу данных графа с библиотекой графов.

Ответ 6

Я тоже пытался это сделать, и я пришел к заключению, что Haskell (для меня), вероятно, не был подходящим инструментом для этой работы.

Ваш вопрос 2 получает:

много ссылок на "те же" данные имеют отдельные копии.

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

Тем не менее, есть несколько методов.

Один из методов заключается в использовании изменяемых объектов для ваших структур. Однако это заставит весь ваш код в монаду.

Вы также можете посмотреть на этот документ Type-Safe Observable Sharing, в котором показано, как использовать некоторые новые языковые функции, поддерживающие ссылки низкого уровня в создавая граф. Их пример - цифровая схема, но я думаю, что это обобщает.

Ответ 7

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