Recursively calling a function, that returns a list, without an empty list case?

Question

Okay, I'll try to give all the info needed here. This is one function of many functions we had to implement in my class in order to solve The Tower of Hanoi. The function in question takes in the 3 towers, in reverse order (biggest>smallest), the number of discs in my problem, and a string, which starts as empty, of the levels of the tower that have already been added to the list.

The function needs to recursively step through each level of the towers and print, in individual strings, what discs are in that level. Hopefully, that makes sense. I can elaborate more if need be.

Here's what I have so far:

stringFromBoardHelper :: Tower -> Tower -> Tower -> Int -> [String] -> [String]
stringFromBoardHelper _ _ _ _ [] = []
stringFromBoardHelper (t1:t1s) (t2:t2s) (t3:t3s) n discString = if n > 0 
        then stringFromBoardHelper t1s t2s t3s (n-1) ((stringFromThreeDiscs t1 t2 t3 n) : discString)
        else discString

My problem is that right now my code just returns the empty list as my function starts with an empty list.

However, if I remove the empty listt case, then I get the error for not having exhaustive cases.Any Ideas?

If the [String] argument represents the work you've already done, then it being empty is not a very good base case! Your base case should be when there is no work left to do, not when all the work remains to be done. Your base case should probably be something meaning "all the pieces are in the place I wanted them already". — amalloy
.. my base case is so blatantly obvious. I can't believe I spent 2 hours on this function. Thank you haha. Saying it the way you did made it click for some reason that my base case should be based on n. — Patrick Conboy

chi chi · Accepted Answer · 2017-10-25T07:58:15

stringFromBoardHelper _ _ _ _ [] = []

This line will apply to any tower, and any n, as long as discString is empty.

It is also the first line in the definition, so it is attempted first.

You probably need to either put that line last, or to specialize the _s so that they match against fewer cases.

(This should solve the primary issue you have -- your code might then have others)

Recursively calling a function, that returns a list, without an empty list case?

1 Answers