I would first and foremost start using pattern-matching.
areListsEqual :: Eq a => [a] -> [a] -> Bool
areListsEqual [ ] [ ] = True
areListsEqual [ ] _ = False
areListsEqual _ [ ] = False
areListsEqual (x:xs) (y:ys) = x == y && areListsEqual xs ys
Note how much more readable this is, when head and tail is avoided.
charlieSort :: Eq a => [[a]] -> [[a]]
charlieSort [ ] = []
charlieSort [x ] = [x]
charlieSort xs@(first:second:theRest)
| areListsEqual xs wip = wip
| otherwise = charlieSort wip
where
swapPairIfNeeded a b
| length a >= length b = [second,first]
| otherwise = [first,second]
modifiedPair = swapPairIfNeeded first second
wip = take 1 modifiedPair ++ charlieSort (drop 1 modifiedPair ++ theRest)
I changed the if-then-else to a guard for slightly improved readability
(YMMV). Instead of checking that the list has at least two elements with a
call to length we use pattern-matching, which also allows us to name
first,second,theRest directly. The name @ pattern pattern both
matches the input against pattern and names the whole input as name.
Now, I want to avoid using take and drop for extracting the two elements
of modifiedPair, so the last two lines are changed into
[shorter,longer] = swapPairIfNeeded first second
wip = [shorter] ++ charlieSort ([longer] ++ theRest)
where you could write the last line as
wip = shorter : charlieSort (longer : theRest)
if you preferred. But why should swapPairIfNeeded return the shorter and
the longer of the first and second list in a list ? Why not use a
pair like
swapPairIfNeeded a b
| length a >= length b = (second,first)
| otherwise = (first,second)
(shorter,longer) = swapPairIfNeeded first second
? In most circumstances, it is better to use tuples for fixed number of
values (possibly of differing types) and to use lists for variable number of
values (necessarily of same type). But it seems strange that
swapPairIfNeeded compares its arguments a and b, but then returns
first and second anyway. In this case, instead of letting it return a
and b in a pair, I will remove swapPairIfNeeded altogether instead :
(shorter,longer)
| length first >= length second = (second,first)
| otherwise = (first,second)
"unfolding" the body of swapPairIfNeeded into the definition of
(shorter,longer).
So now the code of charlieSort looks like
charlieSort :: Eq a => [[a]] -> [[a]]
charlieSort [ ] = []
charlieSort [x ] = [x]
charlieSort xs@(first:second:theRest)
| areListsEqual xs wip = wip
| otherwise = charlieSort wip
where
(shorter,longer)
| length first >= length second = (second,first)
| otherwise = (first,second)
wip = shorter : charlieSort (longer : theRest)
Finally, I should remark that charlieSort doesn't really implement
bubble-sort, because the recursive call to charlieSort will not only
make one "bubble-up" pass along the list, but also fully sort the list
longer : theRest, so that all that has to be done after this recursive call
(before returning one "level up") is to possibly percolate shorter to its
rightful place.
Best Answer
I love your goal, but it's a big job. A couple of hints:
I've worked on GHC, and you don't want any part of the sources. Hugs is a much simpler, cleaner implementation but unfortunately it's in C.
It's a small piece of the puzzle, but Mark Jones wrote a beautiful paper called Typing Haskell in Haskell which would be a great starting point for your front end.
Good luck! Identifying language levels for Haskell, with supporting evidence from the classroom, would be of great benefit to the community and definitely a publishable result!