How to compare multiple strings within in the same list in Haskell

Question

I am trying to write a Haskell function that takes in a list of strings, compares all the strings in the list, and outputs a list of strings that are of the longest length. I want to do this without any predefined functions or imports, I want to try and figure it out all recursively. For example:

    longeststrings["meow","cats","dog","woof"] -> ["meow","cats","woof"]

I know it is a silly example, but I think it proves the point.

I want to do something like

    longeststrings:: [string] -> [string]
    longeststrings []          = []
    longeststrings [x:xs]      = if (x > xs) x:longeststrings[xs]

But I don't know how to only take the largest size strings out of the list, or remove the smallest ones. I would appreciate any help.

Adam Smith · Accepted Answer · 2018-02-09 21:30:21Z

5

you could trivially keep track of the longest length string and an accumulator of values of that length.

longestStrings :: [String] -> [String]
longestStrings = go [] 0
  where
  go acc _ []       = acc  -- base case
  go acc n (x:xs)
    | length x > n  = go [x] (length x) xs
    -- if x is longer than the previously-seen longest string, then set
    -- accumulator to the list containing only x, set the longest length
    -- to length x, and keep looking
    | length x == n = go (x:acc) n xs
    -- if x is the same length as the previously-seen longest string, then
    -- add it to the accumulator and keep looking
    | otherwise     = go acc n xs
    -- otherwise, ignore it

or, as Davislor rightly mentions in the comments, this can be implemented as a fold by teaching the helper function to determine its own longest length

longestStrings :: [String] -> [String]
longestStrings = foldr f []
  where
  f x []        = [x]
  f x yss@(y:_) =
    case compare (length x) (length y) of
      GT -> [x]
      EQ -> x : yss
      LT -> yss

edited Feb 9, 2018 at 21:30

answered Feb 9, 2018 at 21:06

Adam Smith

54.6k13 gold badges84 silver badges120 bronze badges

Sign up to request clarification or add additional context in comments.

12 Comments

Davislor Over a year ago

You don’t even need the extra length argument. If the accumulator is non-empty, the head is (in a tie for) the longest string encountered, so you can take (length . head) acc. Then it could just be a fold.

Davislor Over a year ago

@PushedCrayon One way to avoid where is to write the helper as a lambda, but I’d say that would be more complex. The helper has a different signature than the original function, so it’s got to be separate, and it’s used only inside this function, so it should be nested.

PushedCrayon Over a year ago

@AdamSmith, I am trying to avoid using where because I am trying to get more familiar with functional programming in general, and I have read a lot that using things such as where and let are too close to imperative programming. So I am trying to think of how I could create two separate functions here to get rid of the where. Do you have any ideas? Also, thank you for clarifying acc, it makes much more sense now.

Davislor Over a year ago

Oh no, where is totally good functional style. I’m tempted now to write another example.

PushedCrayon Over a year ago

@AdamSmith I appreciate all of your help! Its hard to know what is or isn't good to read when it comes to new languages and such. But thank you for your insight :)

|

Davislor · Accepted Answer · 2018-02-09 22:43:56Z

As requested, here’s a version with and without the use of where. I think this is a good demonstration of why the advice not to use where is bad advice. I think the first version is a lot easier to understand.

Keep in mind, functional programming isn’t a monastic vow to forswear certain keywords out of masochism. Nor is it a checklist of fashion tips (where is so last season!). “You should avoid that construct arbitrarily because it’s not the ‘functional’ thing to do” really is not how it works. So you shouldn’t uglify your code for the sake of a tip like that.

It is often a good idea to follow the same coding style as other programmers so they will find it easier to understand you. (For example, Adam Smith was subtly trying to train you that acc is a common name for an accumulator and go a common name for a recursive helper function, and they help other programmers figure out the pattern he’s using.) But in fact Haskell programmers do use where, a lot.

Anyway, the code:

longeststrings :: [String] -> [String]
{- Filters all strings as long as any other in the list. -}
longeststrings = foldr go []
  where
    go x [] = [x]
    go x leaders | newlength > record  = [x]
                 | newlength == record = x:leaders
                 | otherwise           = leaders
      where
        record = (length . head) leaders
        newlength = length x

longestStringsUsingLambda :: [String] -> [String]
longestStringsUsingLambda = foldr
    (\x leaders ->
       if leaders == [] then [x]
       else case compare (length x) (length $ head leaders) of
         GT -> [x]
         EQ -> x:leaders
         LT -> leaders )
    []

main :: IO ()
main = let testcases = [ ["meow","cats","dog","woof"],
                         ["foo","bar","baz"],
                         ["meep","foo","bar","baz","fritz","frotz"]
                       ]
       in foldMap print $
          map longestStringsUsingLambda testcases

You can try eliminating the let testcases = ... and see if you consider that an improvement.

Collectives™ on Stack Overflow

How to compare multiple strings within in the same list in Haskell

2 Answers 2

12 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

12 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related