CODEWITHSUNDEEP
haskell
demathieu
demathieu

Reputation: 479

rewriting pseudocode to Haskell

I'm trying to write the pseudo code from beneath into a Haskell function. I was able to write the isValid function, which takes an exam and the current schedule and checks if it the exam would fit into the current schedule. This is my current attempt:

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 []

I know that in my version is not correct but I completely understand what is missing. Also I get this error:

 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)

Pseudo-Code : 

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

Upvotes: 1

Views: 145

Answers (2)

Chad Gilbert
Chad Gilbert

Reputation: 36375

There's some type confusion inside your pseudo-code which is carrying over to your Haskell example and since you have no type annotations, it makes the code hard to reason about, and makes the error messages especially opaque.

Based on what I think you're trying to do, here's an attempt at refining your addExam function in Haskell.

First we need to define the types. From what I infer from your description, you've got a PossibleExam type that will probably have things like Time and Subject fields down the road, but for the example, we only need a type constructor:

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

I'm assuming that your Exam type is just a list of PossibleExams, most likely split up by common subjects.

type Exam = [PossibleExam]

I'm also assuming that the Schedule type is a list of PossibleExams, split up by times to avoid overlap.

type Schedule = [PossibleExam]

You'll avoid a lot of problems by starting off with type signatures on the functions you're creating. Based on my assumptions above, addExam will have a shape like this:

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

If there are no exams left to add, we can return the current Schedule:

addExam currentSchedule [] =
  currentSchedule

And if there are exams left to add, we can do so by using the yet-to-be-defined tryAddExam function (I'll leave it as an exercise to you to figure out what you want to do in case an exam can't be added):

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?

The tryAddExam function can return a Maybe Schedule that represents success with a Just Schedule or failure with Nothing:

tryAddExam :: Schedule -> Exam -> Maybe Schedule

If we've exhausted all possible exams, then we return a failure:

tryAddExam currentSchedule [] =
  Nothing

Otherwise, if there are exams left to attempt, we use your isValid function to test whether we can add them and if so, add them to the current schedule:

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

Hopefully I'm on the right track with your intentions inside the pseudo-code, overlooking some of the array and type confusion in the example. The main thing to get across here is the importance of clearly defining your types and function signatures. Let the types guide you.

Upvotes: 2

Will Ness
Will Ness

Reputation: 71065

A list can not be its own element in Haskell. Even in languages where you can construct such a construct, the only thing you could know about such a thing is that it is a list which is its own element.

On one hand, from your 2nd equation, what fillRes returns is an element of a list that addexam returns.

On the other hand, from your 3rd equation, what addexam returns is the same thing as what fillRes returns. Hence the error.

You can fix it by changing : into ++, as 

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

Of course res ++ [] is just res, and let x = ... in x is just ... (when x isn't referred to inside the ... expression).

Upvotes: 2

Related Questions