2

I did a self-defined data type called Queue and trying to enqueue Integers at the end of the "list".

data Queue = Ele Int Queue | Nil

-- [..] some other Functions

enqueue :: Int -> Queue -> Queue
enqueue x Nil = (Ele x Nil)
enqueue x (Ele _ restEles) = reverse (Ele x reverse restEles)

I get the error:

"Couldn't match expected type Queue' with actual type[a0]'".

I think that is, because the function doesn't know how to handle my datatype. Am I right here? How can I fix this? Do I have to write my own reverse function? And if could you help me with that, because I am still learning Haskell and don't understand this:

reverse = foldl (flip (:)) []
Improve this question
0

3 Answers 3

Reset to default
5

Yes, you have defined a new datatype. Even though it's structurally similar to lists, Haskell will treat it as completely different. So you have to define a new reverse function indeed, or alternatively, define a function converting your type into a standard list and back.

But for enqueue you do not necessarily need reverse. You can just recursively invoke enqueue on restEles in the case for Ele and put the first element back in front of the result.

Here's a pattern for the directly recursive definition for you to complete:

enqueue :: Int -> Queue -> Queue
enqueue x Nil                     = Ele x Nil
enqueue x (Ele firstEle restEles) = ...

For ..., you have to do what I said above: call enqueue recursively on the rest of the elements and put the first elements back on top.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Thanks so far! Im learning Haskell in university and the exercise wants it to be runtime efficient and suggests using reverse for O(n). So recursively I also need to tell the last element of the Queue which is the follower I guess.. Just like setting listpointers in C.
So I got this so far: enqueue :: Int -> Queue -> Queue enqueue x Nil = (Ele x Nil) enqueue x (Ele _ Nil) = --TELL QUEUE THAT NEXT ELE IS NOT NIL enqueue x (Ele _ restEles) = enqueue x restEles< the problem is what I wrote in the commented line.
Ok, I've added another hint. You need only two cases, not three. (By the way, if you use your reverse approach, you need only one case, the separate Nil case is then redundant.)
True.. the first case is just not to waste time. Because when there is no queue I don't need to recurse it 2 times.. Anyway I dont even know if it saves time.. Probably only redundant code as you say.. The problem with your code is that it uses (Ele firstEle restEle), but Queue is defined as (Ele Int Queue).. Or am I just still not getting it?
Ohh one last time... Im sorry! I completely misread the exercise.. They wanted us to program it with the lists of Haskell so using type Queue = [Int] and then it is no problem using reverse.. Thanks anyway for your help, I think I learned something new!
2

The type of reverse is:

reverse :: [a] -> [a]

Queue is not a [a]. You need to implement your own reverseQueue function that understands your data type.

Improve this answer

Comments

1

As for the second part of your question:

reverse :: [a] -> [a]
reverse = foldl (flip (:)) []

First, make sure you understand foldl. It's a powerful high-order function, which means it can be used to implement a lot of other functions (sum,map,filter and of course reverse). You can read about it here.

Now, let's take a look at a simpler version:

reverse :: [a] -> [a]
reverse xs = foldl (\ys y -> y:ys) [] xs

\ys y -> y:ys is a very simple function: it takes a list (ys) and a value (y) and insert the value before the list (y:ys). So our course of plan is: start with the empty list ([]), insert the first item in xs to its left, take the result and insert the second item to its left and so on.

Let's simulate it with a simple list - [1,2,3]:

  1. We start with the empty list - []

  2. Add the first item (1) to it's left: [1]

  3. Add the second item (2) to the left of [1]: [2,1]

  4. Add the third item (3) to the left of [2,1]: [3,2,1]

And we've successfully reversed [1,2,3].

Now, flip is a function that takes a function and "flips" it's arguments. so if subtract a b is a-b, then (flip subtract) a b is equal to subtract b a - b-a. So if (:) is a function that takes an item y and a list ys and adds the item to the beginning of the list, then flip (:) is the same function with flipped arguments - it takes a list and an item, much like our function - \ys y -> y:ys. So we can replace the two of them:

reverse :: [a] -> [a]
reverse xs = foldl (flip (:)) [] xs

And now we write in pointfree style and eliminate xs from both sides of the equation and get the final version:

reverse :: [a] -> [a]
reverse = foldl (flip (:)) []
Improve this answer

2 Comments

Thanks.. I think I know how fold works, but the rest is much clearer to me now.. At least this one foldl (\ys y -> y:ys) [] xs is not so difficult (I just didnt know the \ function) Its hard for me to get how flip can "flip" something without arguments, but a function (:)..
` is not a function - its marks a [lambda expression](http://www.haskell.org/haskellwiki/Anonymous_function). As for flip` - try to play with it in ghci. Create a function of two arguments and see what happens when you flip it. flip is one of these Haskell function which is very simple yet very confusing.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.