[Haskell-cafe] list -> sublists

[Richard O'Keefe]

On Oct 21, 2009, at 3:16 AM, satorisanitarium wrote:

>
> I just started learning haskell and I just came to my first wtf  
> moment.
>
> I'm trying to do something like this:
>
> calling:
> foo 3 [1,2,3,2,4,1,6,3,6,2,3,5,2,5,2,1,6,4]
>
> returns:
> [[1,2,3],[2,4,1,6,3],[2,3]]
>
> but i have no idea how to put something into a sublist.

 From the way you talk about the problem, I suspect that you are
trying to understand in a rather complicated way.

Here's how I approach your example:
     foo item list =
         if there is an occurrence of item in list then
            a new list whose first element is everything up to and  
including
            that occurrence
            and whose remaining elements are found by applying foo  
item to
            everything after that occurrence
         else
            an empty list

We can do this in just a couple of lines using List.elemIndex and  
splitAt,
but let's do it in an elementary way.  We'll write a helper function  
that
either returns (before-and-including-item, after-item) or nothing.

     find_and_split :: Eq t => t -> [t] -> Maybe ([t], [t])

     find_and_split item list = loop list []
       where loop [] _ = Nothing
             loop (x:xs) before | x == item = Just (reverse  
(x:before), xs)
             loop (x:xs) before             = loop xs (x:before)

     foo :: Eq t => t -> [t] -> [[t]]

     foo item list =
       case find_and_split item list of
         Nothing              -> []
         Just (before, after) -> before : foo item after

The answer I get is
*Main> foo 3 [1,2,3,2,4,1,6,3,6,2,3,5,2,5,2,1,6,4]
[[1,2,3],[2,4,1,6,3],[6,2,3]]
                       ^
which differs from yours at the marked place, but which I think is  
right.

List.elemIndex tells you where an element occurs.
Just 0 is the first position.
splitAt splits a list into two pieces, the size argument tells you
the length of the first piece.  So

     foo item list =
       case List.elemIndex item list of
         Nothing  -> []
         Just pos -> before : foo item after
                     where (before, after) = splitAt (pos+1) list

This gives the same answer as the previous version.

In neither case do we do ANYTHING to "put" items into a "sublist",
we just construct a list whose elements happen to be lists.  It's
no different from calculating a list of numbers.