2
\$\begingroup\$

I've written the following explode function using break. The intended behavior is, that a list is divided into sublists by a predicate function, i.e. those elements which match the predicate are the separators - no empty lists should be returned.

Here are some examples:

explode id [True, True, False] = [[False]]
explode id [False, True, False] = [[False], [False]]
explode undefined [] = []
explode id [False, False, True, False] = [[False, False], [False]]
explode (\x -> mod x 3 == 0) [0..10] = [[1,2],[4,5],[7,8],[10]]

The signature of this function is:

explode :: (a -> Bool) -> [a] -> [[a]]

Here is the implementation:

explode _ [] = []
explode f xs
    | null zs = [z]
    | null z  = explode f (tail zs)
    | True    = z : explode f (tail zs)
        where (z, zs) = break f xs

Is there a better way to do this, a maybe more haskell-idiomatic one? Also, what is the complexity of such a function? I believe the running time is linear, but what about the space complexity?

\$\endgroup\$
3
\$\begingroup\$

I like blufox' solution, but remember you can replace explicit recursion by a fold, too:

explode f xs = filter (not.null) $ foldr go [[]] xs where 
  go x (xs:xss) = if f x then []:xs:xss else (x:xs):xss
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I don't like this solution due to the use of foldr. Testing with a very large list (like [1..1000000]) results in a stack overflow, whereas my solution does not. Also it is not faster in cases where it successfully computes the result. Of course I like the beauty of the code, but it's simply not more efficient or correct as my own version - so what is the advantage of this version? \$\endgroup\$ – scravy May 29 '12 at 19:07
  • \$\begingroup\$ @scravy In his favor, you did ask for a Haskell-idiomatic solution. This solution is one such. See my other explanation for why it is idiomatic. \$\endgroup\$ – rahul May 29 '12 at 21:23
  • \$\begingroup\$ @scravy If it's not library code or so, readability is usually more important than anything else. I wouldn't care for the 1000000 elememts case until I really encounter such a list and actually have a performance problem. \$\endgroup\$ – Landei May 30 '12 at 10:55
1
\$\begingroup\$

grouping list separated by some values intuitively seems like a group by operation. That is, abc,def,ghi => (abc)(def)(ghi) So groupBy seems more intuitive for me, and it results in more concise code.

import Data.List

explode fn = filter (nfn . head) . gb
  where nfn = not . fn
        gb = groupBy ((. nfn) . (&&) . nfn)

If you cann't tolerate pointfree, here is the alternate definition for gb

gb = groupBy (\x y -> nfn x && nfn y)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I can tolerate pointfree ;-) - but why should I use this solution at all? I can't see where this code is better to read (= easier to maintain?) or has a better performance (testing shows no difference between my solution and yours). I had a look into the GHC libraries since explode (== ' ') should be the same as words, which is implemented in a rather “ugly” way - reminding me of my own explode function (also using break). So (no offense, I'm curious) why do you guys keep telling me about alternative solutions instead of criticizing my code or explaining in what way these are better? \$\endgroup\$ – scravy May 29 '12 at 19:14
  • \$\begingroup\$ (reached the maximum length of a comment: here's the link to the words-function in GHC.Base haskell.org/ghc/docs/latest/html/libraries/base/src/… ) \$\endgroup\$ – scravy May 29 '12 at 19:16
  • \$\begingroup\$ Because Nature abhors a naked recursion :) ... Seriously, using the fold,map,filter trinity is one of the hallmarks of good functional code. See Real World Haksell the section "Why use folds maps and filters". This almost a given in the community that it is forgotten to explain it explicitly. Another tenet is to use the API where possible rather than inventing your own wheel. Here, I believe that your operation is a special groupBy, which is why I gave this solution. \$\endgroup\$ – rahul May 29 '12 at 21:07
  • 1
    \$\begingroup\$ A final point in their favor is that these higher order operations restrict the behavior, and provide assurances about their interface. That is, a filter never produces lists whose length is greater than given. A map always returns lists which are equal in magnitude, and fold captures the linear decomposition of the problem. So unless your solution has a good reason to use explicit recursion, you might expect these to be the first suggestions :). OTOH, this seems to be a good question you could ask to S.O \$\endgroup\$ – rahul May 29 '12 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.