Problem 9 Solutions

Solution #1

A recursive solution

pack : List a -> List (List a)
pack xs =
    case xs of 
      [] -> 
        []

      y :: ys ->
        pack' y [y] ys


pack' : a -> List a -> List a -> List (List a)
pack' v run xs =
      case xs of 
        [] -> 
          [run]

        y :: ys -> 
          if y == v then
            pack' y (y::run) ys
          else
            (run) :: pack' y [y] ys

Solution #2

Using takeWhile and dropWhile.

pack : List a -> List (List a)
pack xs =
    case xs of
        [] -> 
            []

        hd::tl -> 
            let 
                remainder = dropWhile (\x -> x == hd) tl
            in
                takeWhile (\x -> x == hd) xs :: (pack (remainder))


takeWhile : (a -> Bool) -> (List a) -> (List a)
takeWhile predicate xs =
  case xs of
    [] -> 
        []

    hd::tl  -> 
        if (predicate hd) then
            hd :: takeWhile predicate tl
        else 
            []


dropWhile : (a -> Bool) -> (List a) -> (List a)
dropWhile predicate list =
  case list of
    [] -> 
        []

    hd::tl -> 
        if (predicate hd) then
            dropWhile predicate tl
        else
            list

Solution 3

Another recursive solution.

pack : List a -> List (List a)
pack list =
    case list of
        [] -> 
            []

        x::xs -> 
            let
                y = pack xs
                hd = Maybe.withDefault [] (List.head y)
            in                
                if List.member x hd then
                    (x::hd)::(Maybe.withDefault [] (List.tail y))
                else
                    [x]::y

Solution 4

Fold it!

pack : List a -> List (List a)
pack list =
    List.foldr fPack [] list

fPack : a ->  List (List a) -> List (List a)
fPack x runs = 
    case runs of 
        [] -> [[x]]

        y::ys ->
            case List.head y of
                Nothing -> [[x]] -- we should NEVER get here

                Just rh ->
                    if rh == x then
                        (x :: y) :: ys
                    else 
                        [x] :: runs

Back to Problem 9