CODEWITHSUNDEEP
stringhaskell
Arthur
Arthur

Reputation: 347

How do I add the contents of a string?

Im am making a function which compares two strings to see if one is a rearrangement of the other. for example "hhe" and "heh" would produce true but "hhe" and "hee" would be false. I thought I could do this by summing the elements of the string and seeing if they are the same. I am knew to haskell, so I dont know if I can sum chars like in C. Code so far:

comp :: String -> String-> Bool
comp x y = (sum x) == (sum y)

This produces an error when compiling.

Upvotes: 3

Views: 163

Answers (5)

basic_bgnr
basic_bgnr

Reputation: 737

if you do not want to use standard library(learning purpose) function, you can quickSort both string and check for equality of string (bonus: quickSort)

isEqual :: String -> String -> Bool
isEqual a b = sortString a == sortString b
          where
               sortString :: String -> String 
               sortString [] = []
               sortString (x:xs) = sortString (filter (<x) xs) ++ [x] ++ sortString (filter (>=x) xs)

Upvotes: 0

rampion
rampion

Reputation: 89053

Taking your example code at face value, the problem with it is that Char doesn't implement Num, so sum :: Num a => [a] -> a is incompatible.

We can fix that, however, by using fromEnum to convert the Chars to Ints:

isPermutationOf :: String -> String-> Bool
isPermutationOf x y = hash x == hash y
  where hash = sum . map fromEnum

And this will work on your example case:

λ isPermutationOf "hhe" "heh"
True

The downside is that it also has some false positives:

λ isPermutationOf "AAA" "ab"
True

We can try to reduce those somewhat by making sure that the lengths, maxes, and mins of the inputs are the same:

isPermutationOf :: String -> String-> Bool
isPermutationOf x y = hash x == hash y && maximum x == maximum y && minimum x == minimum y
  where hash = sum . map fromEnum

But though that catches some cases

λ isPermutationOf "AAA" "ab"
False

It doesn't catch them all

λ isPermutationOf "abyz" "acxz"
True

To do that, we really need to make sure we've got the same number of each Char in both inputs. We could solve this by using a Data.Map.Map to store the counts of each Char or by using Data.List.sort to sort each of the inputs, but if we only want to use the Prelude, we'll need to roll our own solution.

There's any number of examples on how to write quicksort in haskell out there, so I'm not going to tell you how to do that. So here's a dumb isPermutationOf that uses math instead.

isPermutationOf xs ys = all (\k -> powsum k as == powsum k bs) [0..n]
  where as = map fromEnum xs
        bs = map fromEnum ys
        n = length xs
        powsum k zs = sum (map (^k) zs)

Basically, we can view an n-length string as a set of n unknowns. isPermutationOf checks the n+1 equations:

  • eq0: x00 + x10 + ... + xn-10 = y00 + y10 + ... + ym-10
  • eq1: x01 + x11 + ... + xn-11 = y01 + y11 + ... + ym-11
  • eq2: x02 + x12 + ... + xn-12 = y02 + y12 + ... + ym-12
  • ...
  • eqn: x0n + x1n + ... + xn-1n = y0n + y1n + ... + ym-1n

eq0 is essentially a length check. Given xs, the other n equations work out to n equations for n unknowns, which will give us a solution for ys unique up to permutation.

But really, you should use a (bucket) sort instead, because the above algorithm is O(n^2), which is slow for this kind of check.

Upvotes: 0

Daniel Wagner
Daniel Wagner

Reputation: 152707

Though there are problems with your implementation, as suggested by others, the direct answer to your question is that you can first convert characters to Int (a type that supports arithmetic) with fromEnum.

> sum . map fromEnum $ "heh"
309

Upvotes: 1

jamshidh
jamshidh

Reputation: 12060

You can first sort, then compare the strings

import Data.List
import Data.Function

comp = (==) `on` sort

which can then be used like this

"abcd" `comp` "dcba" --yields True

Upvotes: 8

Shoe
Shoe

Reputation: 76240

It doesn't make sense to "sum" two strings. Use permutations instead:

comp :: String -> String -> Bool
comp x = (`elem` permutations x)

Live demo

Upvotes: 2

Related Questions