Haskell CodeEval Beautiful Strings

Question

Problem Definition :

When John was a little kid he didn't have much to do. There was no internet, no Facebook, and no programs to hack on. So he did the only thing he could... he evaluated the beauty of strings in a quest to discover the most beautiful string in the world.

Given a string s, little Johnny defined the beauty of the string as the sum of the beauty of the letters in it. The beauty of each letter is an integer between 1 and 26, inclusive, and no two letters have the same beauty. Johnny doesn't care about whether letters are uppercase or lowercase, so that doesn't affect the beauty of a letter. (Uppercase 'F' is exactly as beautiful as lowercase 'f', for example.)

You're a student writing a report on the youth of this famous hacker. You found the string that Johnny considered most beautiful. What is the maximum possible beauty of this string?

Your program should accept as its first argument a path to a filename. Each line in this file has a sentence.

Print out the maximum beauty for the string.

Background :

I'm still very new to Haskell, trying to wrap my head around things like monads and such, so some of the constructs might seem overly simplistic. I would like any sort of criticism from efficiency to idiomatic usage of Haskell. I harbor suspicions that my countSort function is inefficient as I would solve this using a dictionary in an imperative language but that sort of mutable solution seemed out of place in my understanding of Haskell and I couldn't decide if lazy evaluation would make up for it. Either way the speed was actually a bit faster than what I've implemented in imperative languages.

I thought about generalizing the beauty function by moving the toUpper/IsAlpha out of the method to change it's signature to something like [a] -> Int, but it felt outside of the point of the problem, and I honestly couldn't think of a use for this function outside of this problem.

Code :

import Data.List
import Data.Char
import Data.Ord
import System.Environment
countSort :: Ord a => [a] -> [[a]]
countSort x = sortBy (flip $ comparing length) (group $ sort x)
maximumStringBeauty :: String -> Int
maximumStringBeauty x = maximumBeautyInner (countSort . map toUpper $ filter isAlpha x) 26
 where maximumBeautyInner [] _ = 0
 maximumBeautyInner (x : xs) maxVal = (length x) * maxVal + maximumBeautyInner xs (maxVal - 1)
main :: IO ()
main = do
 args <- getArgs
 let path = args !! 0
 file <- readFile path
 putStrLn . unlines . map (show . maximumStringBeauty) . lines $ file

Answer 1

This looks like nice Haskell to me! I'm not an expert, but I could make a few remarks:

• args !! 0 could be simplified to head args. It's just more idiomatic.

• maximumBeautyInner could be renamed to maximumStringBeauty'. That's what I see most of the time, anyway, in this pattern (having an outer "starter" function and an inner "real recursive" function).

• I would write:

  countSort = reverse . sortOn length . group . sort
  

  because it reads nicer, but I'm not sure how expensive the reverse will be afterwards.

• maximumBeautyInner can be written much more concisely when using the builtins sum, zipWith and map. When writing recursive functions, try to see if you can use these and maybe fold or another of their family.

   where maximumBeautyInner = sum . zipWith (*) [26, 25..1] . map length
  

  Step by step:

  • The map length returns only the lengths of the groups (from countSort).

  • The zipWith combines that list with the list [26, 25..1] to form pairs, and applies * to each pair of values. So the first (highest) length gets multiplied by 26, the next one by 25, etcetera.

  • sum, finally, sums them all up (you'd probably guessed).

  You would only pass the result of the countSort to this function, as it is now [[Char]] -> Int.

  By using these list functions, you can reduce the need for your own recursive functions, which increases readability.

All in all, well-factored code, and a good way to solve this problem!

EDIT: instead of using countSort = reverse . sortOn length . group . sort, use countSort = sortOn (negate . length) . group . sort. That removes the need for reverseing the list.

• BlindGarret: Thanks very much for the feedback. A couple of things. Yeah I had the idea to use reverse too but I was really unsure if flipping the comparer would be more efficient and from my imperative background I erred to that side instead. As for the maximumInnerBeauty refactor you are absolutely right. The embarrassing part is I know of and had used all of those functions it just didn't occur to me to use them in that way. Thanks again.
• joranvar: Happy to review! And: no embarassement necessary, I think I still have some recent recursive code lying around that I could enhance with those functions. Sometimes you just need to see it.
• joranvar: I just thought of using negate in countSort: countSort = sortOn (negate . length) . group . sort. That would eliminate the reverse, so we won't have to worry about that anymore. I'll edit the answer.