在Haskell中建模循环调度程序时的非法数据类型上下文

Question

我在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 =>

我该如何解决这个问题？

我还看到了关于删除数据类型上下文的建议,那么如何在不使用数据类型上下文的情况下对调度程序进行建模？

Answer 1

你的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为调度程序添加值,然后请求a 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,尽管存在类型约束,但是需要使用类型对函数进行上下文.