sets need `map` and `filter`

[shriram]

Sets need some kind of map and filter operation. It's onerous to always write it as a fold.

Of course these don't have the same properties as map and filter: they certainly don't "preserve order", but more importantly, map may actually collapse items so the output set size is smaller than that of the input (the filter doesn't have this problem).

Using names like map-like and filter-like would have the dual advantage of signaling it's not exactly the same as map and filter, while retaining discoverability. (By the same token, shouldn't fold also be called fold-like?)

import pick as P

fun set-map-like<T, U>(s :: Set<T>, f :: (T -> U)) -> Set<U>:
  cases (P.Pick) s.pick():
    | pick-none => empty-set
    | pick-some(e, r) => set-map-like(r, f).add(f(e))
  end
end

check:
  fun map-all-to-1(n): 1 end
  set-map-like([set: 1, 2, 3], map-all-to-1) is [set: 1]
end

check:
  fun add-1(n): n + 1 end
  set-map-like([set: 1, 2, 3], add-1) is [set: 3, 4, 2]
end

check:
  set-map-like([set: "Arr", ",", "Hello", "Pyret", "mateys!"], string-length) is [set: 1, 3, 7, 5]
end

fun set-filter-like<T>(s :: Set<T>, f :: (T -> Boolean)) -> Set<T>:
  cases (P.Pick) s.pick():
    | pick-none => empty-set
    | pick-some(e, r) =>
      if f(e):
        set-filter-like(r, f).add(e)
      else:
        set-filter-like(r, f)
      end
  end
end

check:
  fun is-even(n): num-modulo(n, 2) == 0 end
  set-filter-like([set: 1, 2, 3, 4], is-even) is [set: 2, 4]
end