1

我正在建模 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 =>

我该如何解决这个问题？

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

4

2 回答 2

6

你的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，尽管有类型的约束，但需要将上下文放在使用该类型的函数上。

于 2012-12-06T14:33:47.530 回答
3

不建议将约束定义为data定义（请参阅Learn Haskell...）。

最好将约束设置为函数。

（无论如何，您可以设置 DatatypeContexts 修饰符）

于 2012-12-06T12:57:42.723 回答