haleyk100198's blog

Haskell intersection
By haleyk100198, history, 8 years ago, In English

Recently I have been practicing Haskell on CSAcademy, and I was implementing this problem : https://csacademy.com/contest/interview-archive/#task/array-intersection/

Intuitively I tried to use the predefined intersection function to solve the task, yet it does not fit the problem's requirement as it only considers the frequency of the elements showing up in the first list. After googling for a while I found the replacement using xs \ (xs \ ys), yet O(N^2) is not good enough to solve the problem. While the problem could be solved in O(N) by hashing as suggested in the statement, I wonder if there is a predefined way to cope with this task in a Haskell function way? (Dear Haskell god, please spare me from implementing some of the functions)

  • Vote: I like it
  • +19
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

There's an O((N + M) log (N + M)) purely functional solution which relies on the standard Data.Map module. It should be good enough for this problem: 

 
import qualified Data.Map.Strict as Map
listToMap xs = Map.fromListWith (+) (map (\x -> (x, 1)) xs)
mapToList xs = concat (map ((k, v) -> replicate v k) (Map.toList xs))
intersection xs ys = mapToList (Map.intersectionWith min (listToMap xs) (listToMap ys))

The idea is to convert a list to a map that stores a frequency for each element, intersect them using a standard function and convert the result to a list.

I'm not aware of any linear purely functional solution.

→ Reply