Discussion on: Daily Challenge #213 - Are they the "same"?

[Valts Liepiņš]

Solution in Haskell:

import Data.List (sort)

comp :: [Int] -> [Int] -> Bool
comp a b
  | length a == length b = all same $ zip (fmap sq . sort $ a) (sort b)
  | otherwise            = False
  where sq x = x*x
        same x = fst x == snd x

Edit:
I wanted to implement the O(a + b) solution in Haskell as well:

import qualified Data.IntMap.Strict as Map
type Freq = Map.IntMap Int

comp :: [Int] -> [Int] -> Bool
comp as bs
  | length as == length bs = freq (fmap (^2) as) == freq bs
  | otherwise              = False
    where
      freq = foldr inc Map.empty
      inc k = Map.insertWith (+) k 1

[Craig McIlwrath]

Why use all same? Can't you directly test map (^2) (sort a) == sort b?

[Valts Liepiņš]

Wasn't aware that Haskell's equality operator did deep comparision, but that makes sense. Thanks!

I'd probably rewrite this with the O(a + b) algorithm from the other solution.

[Craig McIlwrath]

It's not really deep comparison, it uses the Eq class (==) function. For the primitives, it's by value. For ADTs that derive Eq, it checks equality for all of the values in the ADT, which functions that same as deep comparison.