Неверный контекст типа данных при моделировании циклического планировщика в Haskell

Я моделирую планировщик циклического перебора в Хаскеле.

class Schedulable s where
  isFinal :: s -> Bool

class Scheduler s where
  add :: (Schedulable a) => a -> s -> s
  next :: (Schedulable a) => s -> (a, s)
  empty :: s -> Bool

data Schedulable a => RoundRobin = RoundRobin [a] [a]

instance Scheduler RoundRobin where
  add p (RoundRobin ps qs) = RoundRobin (ps ++ [p]) qs

  next (RoundRobin []     qs) = next (RoundRobin qs [])
  next (RoundRobin (p:ps) qs) = (p, RoundRobin ps (qs ++ [p]))

  empty (RoundRobin [] _) = True
  empty _                 = False

Однако GHC жалуется, что

main.hs:9:6:
    Illegal datatype context (use -XDatatypeContexts): Schedulable a =>

Как я могу решить эту проблему?

Я также видел предложение по удалению контекстов типов данных, так как я могу смоделировать планировщик без использования контекстов типов данных?

2 ответа

Решение

Ваш Scheduler учебный класс

class Scheduler s where
  add :: (Schedulable a) => a -> s -> s
  next :: (Schedulable a) => s -> (a, s)
  empty :: s -> Bool

не собирается работать.

add обещает, что значения любого Schedulable Тип можно добавить в планировщик. Это возможно, но требует расширения, ExistentialQuantification или же GADTs позволил бы определить тип обтекания любого Schedulable значение.

nextОднако обещает поставить ценность любого Schedulable типа, что пожелает звонящий, и это не сработает. Если бы я только добавил Int значения в планировщик, а затем попросите StringКак бы это построить один из воздуха?

Один из способов заставить ваш код работать

{-# LANGUAGE GADTs #-}
module Schedules where

class Schedulable s where
  isFinal :: s -> Bool

class Scheduler s where
  add :: (Schedulable a) => a -> s -> s
  next :: s -> (Schedule, s) -- returns a Schedulable item of unknown type, wrapped in a Schedule
  empty :: s -> Bool

-- Wrapper type for any Schedulable
data Schedule where
    Schedule :: Schedulable a => a -> Schedule

-- Equivalent alternative using existential quantification instead of GADT syntax
-- data Schedule = forall a. Schedulable a => Schedule a

-- make Schedules Schedulable, maybe not necessary
instance Schedulable Schedule where
    isFinal (Schedule s) = isFinal s

-- RoundRobin queues schedulable items, wrapped as Schedules, since lists are homogeneous
data RoundRobin = RoundRobin [Schedule] [Schedule]

-- How RoundRobin works
instance Scheduler RoundRobin where
  -- enqueue item after wrapping it
  add p (RoundRobin ps qs) = RoundRobin (ps ++ [Schedule p]) qs

  -- deliver next item to process
  -- the first equation suggests that (Maybe Schedule, s) would be the better return type
  next (RoundRobin []     []) = error "Nothing to schedule"
  next (RoundRobin []     qs) = next (RoundRobin qs [])
  next (RoundRobin (p:ps) qs) = (p, RoundRobin ps (qs ++ [p]))

  empty (RoundRobin [] _) = True
  empty _                 = False

С помощью GADT синтаксис или экзистенциальная квантификация делает ограничения, наложенные на конструктор, доступными посредством сопоставления с образцом, в отличие от старых DatatypeContexts что, несмотря на ограничения на тип, требуется, чтобы контекст помещался в функции, использующие тип.

Не рекомендуется определять ограничения в data определения (см. Learn Haskell...).

Желательно устанавливать ограничения в функциях.

(В любом случае, вы можете установить модификатор DatatypeContexts)

Другие вопросы по тегам