Haskell: Change string into an all uppercase alpha string using list comprehension

Question

I find list comprehension to be nearly impossible compared to recursion. I'm trying to take a string such as "te1234ST" and return "TEST". Seems easy BUT there are restrictions. Not allowed to use any Haskell predefined functions such as isAlpha and it MUST be list comprehension.

What I have so far, which is pretty terrible for how long I have spent on it:

    convertAllToUpper :: String -> String
    convertAllToUpper xs = [n |n <- xs, check n == True]

          -- This may not even be allowed, and I know it's incorrect anyway
    check :: n -> Bool
    check (n:ns)
        | n `elem` ['a'..'z']       = True
        | n `elem` ['A'..'Z']       = True
        | otherwise         = False

I'm just trying to get this to work and I haven't even started to worry about changing the lower case to upper case yet.

Any points in the right direction would be very very appreciated.

EDIT: Should mention for the conversion from lower to upper can't use: if, then, else. Simply list comprehension and list operators.

Answer 1

It's hard to avoid predefined functions all the way - I assume it's OK to use the list functions defined in the prelude? Here's everything thrown into a list comprehension.

upcaseLetters :: String -> String
upcaseLetters cs =
  [d | c <- cs
     , c `elem` (['a'..'z'] ++ ['A'..'Z']) -- test if `c` is a latin letter.
     , let d = if c `elem` ['A'..'Z']      -- test if `c` is uppercase
               then c
               -- Index into [A..Z] using the index of `c` in [a..z]
               else ['A'..'Z'] !! head [i | (i, x) <- zip [0..] ['a'..'z']
                                          , x == c]]

However, you may feel that using these list functions is cheating. And real programmers avoid any external dependencies. Following this philosophy, we can bootstrap a good portion of the prelude within our list comprehension:

upcaseLetters :: String -> String
upcaseLetters cs =
  [toUpper' c | c <- cs
     , let foldr' _ z []     =  z
           foldr' f z (x:xs) =  f x (foldr' f z xs)

           True ||| _ = True
           _ ||| True = True
           _ ||| _    = False

           elem' e xs = foldr' (|||) False [e==x | x <- xs]

           head' (x:_) = x

           zip' (a:as) (b:bs) =  (a, b) : zip' as bs
           zip' _ _           =  []

           isAlpha' x = x `elem'` (['a'..'z'] ++ ['A'..'Z'])

           isUpper' x = x `elem'` ['A'..'Z']

           toUpper' e
             | isUpper' e = e
             | otherwise  = ['A'..'Z'] !! head' [i | (i, x) <- zip' [0..] ['a'..'z']
                                                   , x == e]
     , isAlpha' c
     ]

This approach combines the clarity of folding with the readability of list comprehensions.

Unfortunately, due to an oversight in the design of the language, Haskell cannot declare new datatypes within the body of a list comprehension. This means that we cannot purge ourselves of our dependency on the prelude's Char, String and Bool types.

Otherwise, [toUpper x | x <- xs , isAlpha x] is what you'd normally want.

Answer 2

Take a look on this

-- The char you want to take into account
valid_char = ['a'..'z'] ++ ['A'..'Z']

-- To filter the other char
valid xs = [ x | x<- xs, v <- valid_char, x==v]

-- Transform the list of valid char in a list of valid upper char 
to_upper xs = [if (x==fst n) then snd n else x | x <- xs, n <- (zip ['a'..'z'] ['A'..'Z']), (x==fst n) || (x==snd n)]  

-- composition of the two preceding function
convert = to_upper . valid

And the test

$ convert "test1234ST" => "TEST"

Answer 3

convertAllToUpper :: String -> String
--                                  This is equivalent to `check n`
convertAllToUpper xs = [n |n <- xs, check n == True]

-- This is a type declaration. Types always begin with a uppercase letter.
-- Therefore "n" can't be valid in this position.
-- You want "check :: Char -> Bool"
check :: n -> Bool
-- This is a pattern match for a list, but you call it with single
-- characters. That can't work.
check (n:ns)
    -- Again, this is the "if foo then true else false" pattern.
    -- This is redundant.
    | n `elem` ['a'..'z']       = True
    | n `elem` ['A'..'Z']       = True
    | otherwise         = False
-- A shorter version of check
check' :: Char -> Bool
check' x = x `elem` ['a'..'z'] ++ ['A'..'Z']

-- when you have written the function `toUpper`
-- (or taken it from Data.Char`) you can simply apply it to
-- every element in the comprehension.
convertAllToUpper' xs = [toUpper n | n <- xs, check n]

Answer 4

Your problem can be broken down into two subproblems:

1. Select only alphabetic characters (characters between 'a' and 'z', or 'A' and 'Z')
2. Convert the lowercase characters to uppercase.

The former can be done with a filter, or a (in a list comprehension) a condition on the element selected. In Unicode (and ASCII) lowercase characters come after uppercase characters, so we can trivially just check whether the character is less than 'a' to determine whether it is uppercase (once we know it's a letter), and all alphabetic characters are in English-alphabet order, so e.g. a lowercase letter is one that's between 'a' and 'z' (inclusive).

With Data.Char (chr, ord):

f xs = [ if x < 'a' then x else chr $ ord x + ord 'A' - ord 'a'
         | x <- xs, (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z') ]

With only Prelude (but would be better written using Data.Map):

f xs = [ if x < 'a' then x else maybe x id $ lookup x charMap
         | x <- xs, (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z') ]
  where charMap = zip ['a' .. 'z'] ['A' .. 'Z']

The right way, of course, is to use the standard library. This can be done quite trivially with some elementary functions:

-- with Data.Char (toUpper, isAlpha)
f xs = [ toUpper x | x <- xs, isAlpha x ]

This is vastly superior in many ways: it is probably faster, and it doesn't rely on ASCII input — it can handle any Unicode character (and in principle any localization: for example, Turkish ‘i’ is correctly capitalized as ‘İ’, not ‘I’ as it would be in ASCII or an English locale, as ‘I’ is the capital of ‘ı’, though I don't know if any Haskell implementations correctly implement this).

Note that list comprehensions are a subset of recursion: if you can manage to write a recursive function of the form:

f []       = []
f (x : xs) = if p x then g x : f xs else f xs 

it can be mechanically converted into a list comprehension of the form:

f xs = [ g x | x <- xs, p x ]

although you can also have multi-variable list expressions, which are a little more complicated to express recursively. Therefore, if you understand recursion, list comprehensions should really be trivial for you.