Skip to content

Instantly share code, notes, and snippets.

@spencerwi
Last active May 16, 2020 03:30
Show Gist options
  • Save spencerwi/cde1c9b002699d0a3952 to your computer and use it in GitHub Desktop.
Save spencerwi/cde1c9b002699d0a3952 to your computer and use it in GitHub Desktop.
Any place I have first-class functions and recursion, I can build foldLeft (reduce), with which I can build map and filter.
function head_and_rest(arr) -- Lua doesn't have a good "slice" function
rest = {}
for i = 2, #arr do -- Lua is 1-indexed
rest[i - 1] = arr[i]
end
return arr[1], rest -- Lua does, however, have multiple-return
end
function copy_and_append(arr, new_val) -- Lua's builtin table insertions are in-place
local copied_table = {unpack(arr)}
copied_table[#copied_table + 1] = new_val
return copied_table
end
function fold_(f, initial, arr)
if (arr == nil or table.getn(arr) == 0) then
return initial
else
local head, rest = head_and_rest(arr)
local next_initial = f(initial, head)
return fold_(f, next_initial, rest)
end
end
function map_(f, arr)
local apply_f = function(previous, current)
return copy_and_append(previous, f(current))
end
return fold_(apply_f, {}, arr)
end
function filter_(predicate, arr)
local drop_if_not_predicate = function(previous, current)
if predicate(current) then
return copy_and_append(previous, current)
else
return previous
end
end
return fold_(drop_if_not_predicate, {}, arr)
end
(defn fold_ [f initial [head & the-rest :as arr]]
(cond
(empty? arr) initial
:else (recur f (f initial head) the-rest)))
(defn map_ [f arr]
(let [applyF (fn [previous current] (conj previous (f current)))]
(fold_ applyF [] arr)))
(defn filter_ [predicate arr]
(let [dropIfNotPredicate (fn [previous current] (if (predicate current) (conj previous current) previous))]
(fold_ dropIfNotPredicate [] arr)))
def fold(initial : A, arr : Array(B), &f : (A,B) -> A) : A forall A,B
if arr.empty?
initial
else
head = arr.first
rest = arr.skip(1)
next_initial = yield initial, head
fold(next_initial, rest, &f)
end
end
def map(arr : Array(A), &f : A -> B) : Array(B) forall A,B
fold([] of B, arr) do |previous, current|
previous << f.call(current)
end
end
def filter(arr : Array(T), &f : T -> Bool) : Array(T) forall T
fold([] of T, arr) do |previous, current|
if f.call(current)
previous << current
else
previous
end
end
end
using System;
using System.Collections.Generic;
using System.Linq;
public class FoldMapAndFilter {
public static A foldL<A,B>(Func<A,B,A> f, A initial, List<B> lst){
if (lst.Count == 0){
return initial;
} else {
return FoldMapAndFilter.foldL(f, f(initial, lst.First()), lst.Skip(1).ToList());
}
}
public static List<B> map<A,B>(Func<A,B> f, List<A> lst) {
Func<List<B>, A, List<B>> applyF = (List<B> prev, A current) => {
var copy = new List<B>(prev);
copy.Add(f(current));
return copy;
};
return FoldMapAndFilter.foldL(applyF, new List<B>(), lst);
}
public static List<A> filter<A>(Func<A,bool> predicate, List<A> lst) {
Func<List<A>, A, List<A>> dropIfNotPredicate = (List<A> prev, A current) => {
if (predicate(current)){
var copy = new List<A>(prev);
copy.Add(current);
return copy;
} else {
return prev;
}
};
return FoldMapAndFilter.foldL(dropIfNotPredicate, new List<A>(), lst);
}
}
// "A delegate (A,B) f" is the dlang way of saying "f: (A,B) => A"
A foldL(A,B)(scope A delegate (A, B) f, A initial, B[] arr){
if (arr.length == 0){
return initial;
} else {
return foldL(f, f(initial, arr[0]), arr[1..$]);
}
}
B[] map(A,B)(scope B delegate (A, B) f, A[] arr) {
auto applyF = (B[] previous, A current) => previous ~ [f(current)];
foldL(applyF, [], arr);
}
A[] filter(A)(scope bool delegate (A) predicate, A[] arr) {
auto dropIfNotPredicate = delegate (A[] previous, A current) {
if (predicate(current)) {
return (previous ~ [current]);
} else {
return previous;
}
};
foldL(dropIfNotDelegate, [], arr);
}
fold(Function f, initial, List arr){
if (arr.isEmpty){
return initial;
} else {
return fold(f, f(initial, arr[0]), arr.sublist(1));
}
}
List map(Function f, List arr){
var applyF = (List prev, current) => prev.sublist(0).add(f(prev));
return fold(applyF, [], arr);
}
List filter(Function predicate, List arr){
var dropIfNotPredicate = (List prev, current) => predicate(current) ? prev.sublist(0).add(current) : prev;
return fold(dropIfNotPredicate, [], arr);
}
var fold = function fold(f, initial, [head, ...rest]){
if (head) {
return fold(f, f(initial, head), rest);
} else {
return initial;
}
}
var map = function map(f, array){
var applyF = (previous, current) => previous.concat(f(current));
return fold(applyF, [], array);
}
var filter = function filter(predicate, array){
var dropIfNotPredicate = (previous, current) => predicate(current) ? previous.concat(current) : previous;
return fold(dropIfNotPredicate, [], array);
}
defmodule FoldMapAndFilter do
def fold_(f, initial, []) do
initial
end
def fold_(f, initial, arr) do
[head | tail] = arr
fold_(f, f.(initial, head), tail)
end
def map_(f, arr) do
applyF = fn(previous, current) -> previous ++ [f.(current)] end
fold_(applyF, [], arr)
end
def filter_(predicate, arr) do
dropIfNotPredicate = fn(previous, current) -> if predicate.(current) do previous ++ [current] else previous end end
fold_(dropIfNotPredicate, [], arr)
end
end
let rec fold' f initial arr =
match arr with
[] -> initial
| head :: rest -> fold' f (f initial head) rest
;;
let map' f arr =
let applyF previous current =
previous @ [(f current)])
in
fold' applyF [] arr;;
let filter' predicate arr =
let dropIfNotPredicate previous current =
if (predicate current) then
previous@[current]
else previous
in
fold' dropIfNotPredicate [] arr;;
module FoldMapAndFilter where
foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f initial [] = initial
foldl' f initial arr@(x:rest) = foldl' f (f initial x) rest
map' :: (a -> b) -> [a] -> [b]
map' f arr = foldl' applyF [] arr
where applyF previous current = previous ++ [(f current)]
filter' :: (a -> Bool) -> [a] -> [a]
filter' predicate arr = foldl' dropIfNotPredicate [] arr
where dropIfNotPredicate previous current | predicate current = previous ++ [current]
| otherwise = previous
import java.util.function.Function;
import java.util.function.BiFunction;
import java.util.List;
import java.util.ArrayList;
public class FoldMapAndFilter {
public static <A,B> A foldL(BiFunction<A,B,A> f, A initial, List<B> lst){
if (lst.isEmpty()){
return initial;
} else {
return foldL(f, f.apply(initial, lst.get(0)), new ArrayList<>(lst.subList(1, lst.size())));
}
}
public static <A,B> List<B> map(Function<A,B> f, List<A> lst){
BiFunction<List<B>, A, List<B>> applyF = (previous, current) -> {
List<B> copy = new ArrayList<>(previous);
copy.add(f.apply(current));
return copy;
};
return FoldMapAndFilter.foldL(applyF, new ArrayList<>(), lst);
}
public static <A> List<A> filter(Function<A,Boolean> predicate, List<A> lst){
BiFunction<List<A>, A, List<A>> dropIfNotPredicate = (previous, current) -> {
List<A> copy = new ArrayList<>(previous);
if (predicate.apply(current)){
copy.add(current);
}
return copy;
};
return FoldMapAndFilter.foldL(dropIfNotPredicate, new ArrayList<>(), lst);
}
}
var fold = function fold(f, initial, array){
if (array && array.length > 0) {
var head = array[0],
rest = array.slice(1);
return fold(rest, f, f(initial, head))
} else {
return initial;
}
}
var map = function(f, array){
var applyF = function(previous, current){
return previous.concat(f(current));
}
return fold(applyF, [], array);
}
var filter = function(predicate, array){
var dropIfNotPredicate = function(previous, current){
if (predicate(current)){
return previous.concat(current);
} else {
return previous;
}
}
return fold(dropIfNotPredicate, [], array);
}
fun <A, B> fold(f: (A, B) -> A, initial: A, arr: List<B>) : A {
if (arr.isEmpty()) {
return initial;
} else {
val head = arr.first();
val rest = arr.drop(1);
return fold(f, f(initial, head), rest);
}
}
fun <A, B> map(f: (A) -> B, arr: List<A>): List<B> {
val applyF = {previous : List<B>, current : A ->
previous.plusElement(f(current));
};
return fold(applyF, emptyList(), arr);
}
fun <T> filter(predicate: (T) -> Boolean, arr: List<T>) : List<T> {
val dropIfNotPredicate = {previous : List<T>, current : T ->
if (predicate(current)) {
previous.plusElement(current);
} else {
previous;
}
};
return fold(dropIfNotPredicate, emptyList(), arr);
}
let rec fold' f initial = function
| [] -> initial
| head :: rest -> fold' f (f initial head) rest
let map' f arr =
let applyF previous current =
previous @ [(f current)]
in
fold' applyF [] arr
let filter' predicate arr =
let dropIfNotPredicate previous current =
if (predicate current) then
previous@[current]
else
previous
in
fold' dropIfNotPredicate [] arr
def fold(f, initial, array):
if not array:
return initial
else:
head = array[0]
rest = array[1:]
return fold(f, rest, f(initial, head))
def map_(f, array):
def applyF(previous, current):
return list(previous).append(f(current))
return fold(applyF, [], array)
def filter_(predicate, array):
def dropIfNotPredicate(previous, current):
if (predicate(current)):
return list(previous).append(current)
else:
return list(previous)
return fold(dropIfNotPredicate, [], array)
def fold_(initial, arr, &f)
if arr.empty? then
initial
else
head = arr.first
rest = arr.drop(1)
next_initial = yield initial, head
fold_(next_initial, rest, &f)
end
end
def map_(arr, &f)
fold_([], arr) do |previous, current|
previous << f.call(current)
end
end
def filter_(arr, &predicate)
fold_([], arr) do |previous, current|
if predicate.call(current)
previous + [current]
else
previous
end
end
end
def fold_[A,B](f: (A, B) => A, initial: A, arr: List[B]) : A = arr match {
case head :: rest => fold_(f, (f(initial, head)), rest)
case _ => initial
}
def map_[A,B](f: A => B, arr: List[A]) : List[B] = {
def applyF(previous: List[B], current: A) = previous ++ List(f(current));
return fold_(applyF, List(), arr);
}
def filter_[A](predicate: A => Boolean, arr: List[A]) : List[A] = {
def dropIfNotPredicate(previous: List[A], current: A) = if (predicate(current)) previous ++ List(current) else previous;
return fold_(dropIfNotPredicate, List(), arr);
}
import Foundation
func fold<A,B>(initial : A, into arr: Array<B>, with combiner: (A, B) -> A) -> A {
guard !(arr.isEmpty) else {
return initial
}
let head = arr.first!
let rest = arr.dropFirst(1)
let next_initial = combiner(initial, head)
return fold(initial: next_initial, into: Array<B>(rest), with: f)
}
func map<A,B>(from: Array<A>, with transformer: (A) -> B) -> Array<B> {
func applyTransformer(previous : Array<B>, current: A) -> Array<B> {
// There's a quirk of Swift's type system where declaring previous as an inout param messes with the casting needed to allow this function to be passed into fold.
// So instead, we just make a new Array so that we don't have to mutate `previous` and thus don't have to declare it as inout.
var new = Array<B>(previous)
new.append(transformer(current))
return new
}
return fold(initial: Array<B>(), into: from, with: applyTransformer)
}
func filter<T>(from: Array<T>, matching: (T) -> Bool) -> Array<T> {
func dropIfNotMatching(previous: Array<T>, current: T) -> Array<T> {
// There's a quirk of Swift's type system where declaring previous as an inout param messes with the casting needed to allow this function to be passed into fold.
// So instead, we just make a new Array so that we don't have to mutate `previous` and thus don't have to declare it as inout.
var new = Array<T>(previous)
if matching(current) {
new.append(current)
}
return new
}
return fold(initial: Array<T>(), into: from, with: dropIfNotMatching)
}
@spencerwi
Copy link
Author

So far, I'm most surprised at how foreign it was to write a higher-order function in Ruby; in searching around, I found a bunch of people confused by Ruby's multiple concepts of blocks, procs, and lambdas. Eventually I just went with f.call and passing lambdas around in map_ and filter_

Higher-order functions are also not particularly idiomatic in Python, which is unusual for a list/dictionary-oriented language. They get away with mostly using comprehensions though.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment