Clever Geek Handbook

How do I add the content of the string?

I am making a function that compares two strings to see if it is a rearrangement of the other. for example, "hhe" and "heh" will return true, but "hhe" and "hee" will be false. I thought I could do this by summing the elements of the string and seeing if they are the same. I know haskell, so I don't know if I can sum characters like in C. Code:

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

This results in a compilation error.

+3


source to share


5 answers


You can sort first, then compare strings

import Data.List
import Data.Function

comp = (==) `on` sort


which can then be used this way

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


source


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

:

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


Live demo

+2


source


While 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
+1


source


Taking your example code at face value, the problem with it is that it Char

doesn't implement Num

, so it's sum :: Num a => [a] -> a

incompatible.

We can fix this, however, by using fromEnum

to convert Char

to Int

s:

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

And this will work in your example:

λ isPermutationOf "hhe" "heh"
True

The downside is that it also has some false positives:

λ isPermutationOf "AAA" "ab"
True

We can try to reduce them a little 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 although it catches some cases

λ isPermutationOf "AAA" "ab"
False

He won't catch them all

λ isPermutationOf "abyz" "acxz"
True

To do this, we really need to make sure that we have the same amount of each Char

on both inputs. We could solve this problem by using Data.Map.Map

the storage of samples for each Char

or use Data.List.sort

for sorting each of the inputs, but if we only want to use Prelude

, we will need to turn our own decision.

There's any number of examples of writing quicksort

in haskell out there , so I won't tell you how to do it. So, here's a dumb isPermutationOf

one 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 the n

-length string as a collection of n

unknowns. isPermutationOf

checks the equations n+1

:

  • eq 0: x 00 + x 10 + ... + x n-10 = y 00 + y 10 + ... + y m-1 0
  • eq 1: x 01 + x 11 + ... + x n-11 = y 01 + y 11 + ... + y m-1 1
  • eq 2: x 02 + x 12 + ... + x n-12 = y 02 + y 12 + ... + y m-1 2
  • ...
  • eq n: x 0n + x 1n + ... + x n-1n = y 0n + y 1n + ... + y m-1 n

eq0

is essentially a length check. Considering xs

other equations n

develop equations n

for n

unknowns, which will give us a solution for a ys

unique one up to permutation.

But actually you should use a (bucket) sort because the above algorithm O(n^2)

is slow for this type of check.

0


source


if you don't want to use a standard library function (learning target) you can quickly concatenate both strings and check for string equality (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)
0


source






More articles:


All Articles