CODEWITHSUNDEEP
haskellrecursionfunctional-programming
Bob Fang
Bob Fang

Reputation: 7411

Functionally solving questions: how to use Haskell?

I am trying to solve one of the problem in H99: Split a list into two parts; the length of the first part is given.

Do not use any predefined predicates.

Example:

> (split '(a b c d e f g h i k) 3)
( (A B C) (D E F G H I K))

And I can quickly come with a solution:

split'::[a]->Int->Int->[a]->[[a]]
split' [] _ _ _     = []
split' (x:xs) y z w = if y == z then [w,xs] else split' xs y (z+1) (w++[x])

split::[a]->Int->[[a]]
split x y = split' x y 0 []

My question is that what I am doing is kind of just rewriting the loop version in a recursion format. Is this the right way you do things in Haskell? Isn't it just the same as imperative programming?

EDIT: Also, how do you generally avoid the extra function here?

Upvotes: 2

Views: 225

Answers (3)

vlastachu
vlastachu

Reputation: 257

split'::[a]->Int->([a],[a])

split' [] _ = ([],[])
split' xs 0 = ([],xs)
split' (x:xs) n = (x:(fst splitResult),snd splitResult) 
                  where splitResult = split' xs (n-1)

It seems you have already shown an example of a better solution.

I would recommend you read SICP. Then you come to the conclusion that the extra function is normal. There's also widely used approach to hide functions in the local area. The book may seem boring to you but in the early chapters she will get used to the functional approach in solving problems.

There are tasks in which the recursive approach is more necessary. But for example if you use tail recursion (which is so often praised without cause) then you will notice that this is just the usual iteration. Often with "extra-function" which hide iteration variable (oh.. word variable is not very appropriate, likely argument).

Upvotes: -1

daniel gratzer
daniel gratzer

Reputation: 53901

It's not the same as imperative programming really, each function call avoids any side effects, they're just simple expressions. But I have a suggestion for your code

split :: Int -> [a] -> ([a], [a])
split p xs = go p ([], xs)
  where go 0 (xs, ys) = (reverse xs, ys)
        go n (xs, y:ys) = go (n-1) (y : xs, ys)

So how we've declared that we're only returning two things ([a], [a]) instead of a list of things (which is a bit misleading) and that we've constrained our tail recursive call to be in local scope.

I'm also using pattern matching, which is a more idiomatic way to write recursive functions in Haskell, when go is called with a zero, then the first case is run. It's more pleasant generally to write recursive functions that go down rather than up since you can use pattern matching rather than if statements.

Finally this is more efficient since ++ is linear in the length of the first list, which means that the complexity of your function is quadratic rather than linear. This method is also tail recursive unlike Daniel's solution, which is important for handling any large lists.

TLDR: Both versions are functional style, avoiding mutation, using recursion instead of loops. But the version I've presented is a little more Haskell-ish and slightly faster.

A word on tail recursion

This solution uses tail recursion which isn't always essential in Haskell but in this case is helpful when you use the resulting lists, but at other times is actually a bad thing. For example, map isn't tail recursive, but if it was you couldn't use it over infinite lists!

In this case, we can use tail recursion, since an integer is always finite. But, if we only use the first element of the list, Daniel's solution is much faster, since it produces the list lazily. On the other hand, if we use the whole list, my solution is much faster.

Upvotes: 3

Daniel Lyons
Daniel Lyons

Reputation: 22803

It's convenient that you can often convert an imperative solution to Haskell, but you're right, you do usually want to find a more natural recursive statement. For this one in particular, reasoning in terms of base case and inductive case can be very helpful. So what's your base case? Why, when the split location is 0:

split x 0 = ([], x)

The inductive case can be built on that by prepending the first element of the list onto the result of splitting with n-1:

split (x:xs) n = (x:left, right)
  where (left, right) = split xs (n-1)

This may not perform wonderfully (it's probably not as bad as you'd think) but it illustrates my thought process when I first encounter a problem and want to approach it functionally.

Edit: Another solution relying more heavily on the Prelude might be:

split l n = (take n l, drop n l)

Upvotes: 6

Related Questions