将伪代码重写为Haskell

Question

我正试图从下面将伪代码写入Haskell函数。我能够编写isValid函数，它接受一个考试和当前时间表，并检查考试是否符合当前时间表。这是我目前的尝试：

addexam currentSchedule [] = currentSchedule
addexam currentSchedule listOfExams = let result = []
                                          res = fillRes currentSchedule listOfExams
                                       in (res: result)
fillRes currentSchedule (x:xs) | isValid x currentSchedule = addexam (x:currentSchedule) xs
                               | otherwise = addexam currentSchedule []

我知道我的版本不正确，但我完全理解缺少什么。我也得到这个错误：

 Occurs check: cannot construct the infinite type: t ~ [t]
    Expected type: [t] -> [t] -> t
      Actual type: [t] -> [t] -> [t]
    Relevant bindings include
      res :: t (bound at Server.hs:170:43)
      listOfExams :: [t] (bound at Server.hs:169:25)
      currentSchedule :: [t] (bound at Server.hs:169:9)
      addexam :: [t] -> [t] -> [t] (bound at Server.hs:168:1)
    In the expression: fillRes currentSchedule listOfExams
    In an equation for ‘res’: res = fillRes currentSchedule listOfExams
    In the expression:
      let
        result = []
        res = fillRes currentSchedule listOfExams
      in (res : result)

伪代码：

addExam (currentSchedule, examsLeft):
    if examsLeft.empty():
        return [currentSchedule]
    doodle = examsLeft[0]
    results = []
    for each possible-exam in doodle
        if is-valid (possible-exam, currentSchedule):
            res = addExam (currentSchedule.append(possible-exam), examsLeft[1:])
        results.append(res)
    return results 

Answer 1

伪代码中存在一些类型混淆，这些混淆将延续到Haskell示例中，并且由于没有类型注释，因此很难对代码进行推理，并使错误消息特别不透明。

基于我认为您正在尝试做的事情，这里有一个在Haskell中改进addExam函数的尝试。

首先，我们需要定义类型。根据我从你的描述中推断，你已经得到了一个PossibleExam类型，它可能会有Time和Subject字段，但对于这个例子，我们只需要一个类型构造函数：

data PossibleExam = PossibleExam -- you'll probably have other fields like Time, Subject, etc.

我假设你的Exam类型只是PossibleExams的列表，很可能是按常见主题划分的。

type Exam = [PossibleExam]

我还假设Schedule类型是PossibleExams的列表，按时间划分以避免重叠。

type Schedule = [PossibleExam]

从创建函数的类型签名开始，可以避免很多问题。根据我上面的假设，addExam将具有这样的形状：

addExam :: Schedule -> [Exam] -> Schedule

如果没有考试可添加，我们可以返回当前时间表：

addExam currentSchedule [] =
  currentSchedule

如果还有考试要添加，我们可以使用尚未定义的tryAddExam函数来完成（我将把它作为一个练习留给你，以确定在无法添加考试的情况下你想做什么）：

addExam currentSchedule (doodle:examsLeft) =
  case tryAddExam currentSchedule doodle of
    Just newSchedule ->
      addExam newSchedule examsLeft
    Nothing -> 
      undefined -- What do you do if the exam won't fit? 

tryAddExam函数可以返回代表Just Schedule成功或Nothing:失败的Maybe Schedule

tryAddExam :: Schedule -> Exam -> Maybe Schedule

如果我们已经用尽了所有可能的考试，那么我们会返回一个失败：

tryAddExam currentSchedule [] =
  Nothing

否则，如果还有考试要尝试，我们将使用您的isValid功能来测试是否可以添加它们，如果可以，则将它们添加到当前时间表中：

tryAddExam currentSchedule (possibleExam:rest) =
  if isValid possibleExam currentSchedule then
    Just $ possibleExam : currentSchedule
  else
    tryAddExam currentSchedule rest

希望我在伪代码中的意图是正确的，忽略了示例中的一些数组和类型混淆。这里要传达的主要内容是明确定义类型和函数签名的重要性。让类型来指导你。

Answer 2

在Haskell中，列表不能是它自己的元素。即使在可以构造这样一个构造的语言中，关于这样一个东西，你唯一能知道的就是它是一个列表，它是自己的元素。

一方面，根据第二个等式，fillRes返回的是addexam返回的列表中的一个元素。

另一方面，根据您的第三个等式，addexam返回的内容与fillRes返回的内容相同。因此出现了错误。

您可以通过将:更改为++来修复它，作为

addexam currentSchedule listOfExams = let result = []
                                          res = fillRes currentSchedule listOfExams
                                       in res ++ result

当然，res ++ []只是res，而let x = ... in x只是...（当x在...表达式中没有被引用时）。