list understanding and recursive if statements in Haskell

Question

I'm currently practicing Haskell in a number of ways. using lists to create a ton of fun things. Now I'm (think) having problems with understanding if statements.

What I want to do is make a Focuslist that shifts the focus to the most left item. Focuslists are already quite tricky, essentially being two independent lists. And it also splits the whole list in half, and reverses the back list.

For instance. If you want to make a focuslist of [0,1,2,3,4,5], and want a focus on 3, The focuslist will be [3,4,5][2,1,0].

I've already made three specific functions. One that makes the focuslist datatype:

data FocusList a = FocusList { forward :: [a], backward :: [a]}

With which you can call it by using

fromList :: [a] -> FocusList a
fromList list = FocusList list []

One that changes it back to a list from a focuslist:

toList :: FocusList a -> [a] 
toList (FocusList fw bw) = reverse bw ++ fw

and one that shifts it to left once, changes [0,1,2,3,4,5] to [0,1,2,3,4,5] which now looks like [2,3,4,5][0,1] as focuslist:

goLeft :: FocusList a -> FocusList a
goLeft (FocusList fw (f:bw)) = FocusList (f:fw) bw

Now, to the main point. If I were to shift it all the way to the left. I want to use goLeft until the length of the list is 1. I was thinking of using a recursive if statement until the length of the first list equals to one. and using goLeft if it was not one.

So i thought of a simple if statement. Which (for now) doesn't work at all. it uses leftMost :: FocusList a -> FocusList a

leftMost (FocusList fw (f:bw)) =  if (length (FocusList fw) == 1)
                                    then FocusList (f:fw) bw
                                    return leftMost
                                   else FocusList fw (f:bw)

I was thinking of it the pythonic way. Which doesn't seem to work. How do I make it logically recursive?

user_3234959 · Answer

Don't use length, it costs O(N) since it has to scan the whole list. If you instead use pattern matching, in this case you only pay a O(1) cost.

A simple approach is to use two equations, which are tried one after the other one.

leftMost :: FocusList a -> FocusList a
-- if there's only one backward item, leave the list as it is
leftMost (FocusList fw [f]) = FocusList fw [f]
-- otherwise, goLeft, then recurse
leftMost fl                 = leftMost (goLeft fl)

The pattern [f] only matches lists with a single item. It's equivalent to (f:[]).

Note that the code above will crash if the backward part is empty. If that's an issue, you'll need to handle that by adding more equations.

Alternatively, one can shorten the code using an as-pattern:

leftMost :: FocusList a -> FocusList a
leftMost fl@(FocusList fw [f]) = fl    -- fl is the whole input
leftMost fl                    = leftMost (goLeft fl)

We can also inline goLeft, if we wish:

leftMost :: FocusList a -> FocusList a
leftMost fl@(FocusList fw [f]) = fl
leftMost (FocusList fw (f:bw)) = leftMost (FocusList (f:fw) bw)

Or even handle the empty-backward-list issue mentioned above:

leftMost :: FocusList a -> FocusList a
leftMost fl@(FocusList fw     [f])    = fl
leftMost    (FocusList fw     (f:bw)) = leftMost (FocusList (f:fw) bw)
leftMost    (FocusList (f:fw) [])     = FocusList fw [f]
leftMost    (FocusList []     [])     = error "leftMost: empty list"

The last case, referring to an empty list, is hard to handle in a sensible way. You can choose to crash with an error message (as done above), return the empty list (is that the intended result?), or report the error to the caller by returning a Maybe (FocusList a) instead.

list understanding and recursive if statements in Haskell

1 Answers