map.hs

import Data.List ((\\))
import qualified Data.Map as Map

prune :: Ord k => Map.Map k k -> Map.Map k k
prune m = _prune m orphans
  where
    _prune m [] = m
    _prune m os = prune $ foldl (flip Map.delete) m os
    orphans = (Map.keys m) \\ (Map.elems m)

{-
import qualified Data.Map.Lazy as Map
let sample = Map.fromList [(1,3), (2,1), (3,1), (4,5), (5,5), (6,4), (7,6)]
prune sample
-}

map.rb

class Map
  def initialize(pairs)
    @relations = pairs.each_with_object({}) do |(a,b), rel|
      rel[a] = b
    end
  end

  def map(a)
    @relations[a]
  end

  def prune
    os = orphans
    return self if os.empty?

    self.class.new(@relations.reject{|x,_| os.include? x }).prune
  end

  def orphans
    @relations.keys - @relations.values
  end

  def one_to_one?
    duplicates.empty?
  end

  def duplicates
    reverse.select {|b, as| as.count > 1 }
  end

  def reverse
    @relations.map{|a,b| [b,a]}.each_with_object({}) {|(b,a), h| (h[b] ||= []) << a }
  end
end

map = Map.new [[1,3], [2,1], [3,1], [4,5], [5,5], [6,4], [7,6]]
map.prune
map.prune.one_to_one?