0

Was wondering if you could help me, I'm writing a haskell program and im using the transpose method and its working as I wish. But I then wish to check each [string] returned from the transpose is of the same charcter e.g

transpose["hello","help","hell","helm"]

would return something like 

["hhhh","eeee","llll","plml","o"]

I wonder is it then possible to go through each the above and stopping when the string isn't of all the same characters e.g stoping at "plml"

Frank Lexer
  • 310
  • 1
  • 11
K.Madden
  • 353
  • 1
  • 16
  • 3
    Sounds like you should be using [takeWhile](https://hackage.haskell.org/package/base-4.12.0.0/docs/Prelude.html#v:takeWhile). I'll leave you to come up with a suitable predicate function (which you could for example write with a fairly simple direct recursion). – Robin Zigmond Dec 10 '19 at 00:14
  • Could this then be essentially used to get the longest common prefix? – K.Madden Dec 10 '19 at 00:25
  • Is something like autocompletion, you start enter a world and you have a list of words start with same letters ? – Andrelec1 Dec 10 '19 at 00:26
  • It’s a longest common prefix problem I’m trying to perform – K.Madden Dec 10 '19 at 00:30
  • Give this a try `takeWhile ((==1) . length . nub)`. Sorry for the curt comment, I'm in a lecture ;) – MikaelF Dec 10 '19 at 01:04
  • 3
    @MikaelF `nub` is needlessly expensive if all you want to know is that there's exactly one element. You could instead use `all` to test whether each element of the list is equal to the list's first element. – amalloy Dec 10 '19 at 01:17
  • @amalloy so how do you mean to go about it? Still use a takeWhile? – K.Madden Dec 10 '19 at 01:26
  • Related: [Test if all elements of a Foldable are the same](https://stackoverflow.com/q/55815807/7509065) – Joseph Sible-Reinstate Monica Dec 10 '19 at 01:31

1 Answers1

4

One way of doing it is to apply group to each string:

> group "hhhh"
["hhhh"]
> group "plml"
["p","l","m","l"]

Then, if you takeWhile the group count is 1, you'll get all the homogeneous strings:

> test = ["hello","help","hell","helm"]
> import Data.List
> takeWhile ((==1) . length) . map group . transpose $ test
[["hhhh"],["eeee"],["llll"]]

You can get rid of the extra list layer with map head.

Also, it would actually be better to replace this test for single groups with a custom pattern match function:

single :: [a] -> Bool
single [a] = True
single _ = False

and use:

> map head . takeWhile single . map group . transpose $ test
["hhhh","eeee","llll"]]

The main difference is that (==1) . length needs to evaluate and count the length of the whole set of groups, but single can stop early. For example, on an infinite string:

> ((==1) . length) $ group $ "aaa" ++ repeat 'b'  -- hangs forever
> single $ group $ "aaa" ++ repeat 'b'  -- returns `False` at first 'b'

An alternative, suggested in the comments, would be to do a more direct check that the first character is equal to all the other characters:

allSame :: (Eq a) => [a] -> Bool
allSame (x:rest) = all (==x) rest

and:

> takeWhile allSame . transpose $ test
["hhhh","eeee","llll"]

SPOILERS: As per your comments, you're trying to find the longest prefix, so to finish things off, note that you want to map head across:

["hhhh","eeee","llll"]

to get:

['h','e','l']

which is the same as:

"hel"

Since map head followed by map head can be written map head . map head, or even shorter map (head . head), the final definition using group can be written:

prefix :: (Eq a) => [[a]] -> [a]
prefix = map (head . head) . takeWhile single . map group . transpose
   where single [a] = True
         single _ = False

and the final definition using allSame can be written:

prefix :: (Eq a) => [[a]] -> [a]
prefix = map head . takeWhile allSame . transpose
   where allSame (x:rest) = all (==x) rest
K. A. Buhr
  • 45,621
  • 3
  • 45
  • 71
  • Amazing! thank you so much. If you don't mind could you possibly give a quick breakdown of the line 'prefix = map (head . head) . takeWhile single . map group . transpose' as in how it works on the string – K.Madden Dec 15 '19 at 13:21