Q: Can I build a "pure" functional map in Go without using builtin map? A: Maybe

list.go

package mymap

type List func() (frontFunc, restFunc, emptyFunc)

type frontFunc func() (string, string)
type restFunc func() List
type emptyFunc func() bool

func NewList() List {
	front := func() (string, string) {
		panic("front of empty list!")
	}

	rest := func() List {
		panic("rest of empty list!")
	}

	empty := func() bool {
		return true
	}

	return List(func() (frontFunc, restFunc, emptyFunc) {
		return frontFunc(front), restFunc(rest), emptyFunc(empty)
	})
}

func LFront(l List) (string, string) {
	front, _, _ := l()
	return front()
}

func LRest(l List) List {
	_, rest, _ := l()
	return rest()
}

func LEmpty(l List) bool {
	_, _, empty := l()
	return empty()
}

func LAdd(l List, k, v string) List {
	front := func() (string, string) {
		return k, v
	}

	rest := func() List {
		return l
	}

	empty := func() bool {
		return false
	}

	return List(func() (frontFunc, restFunc, emptyFunc) {
		return frontFunc(front), restFunc(rest), emptyFunc(empty)
	})
}

func LForEach(l List, do func(string, string)) {
	if LEmpty(l) {
		return
	}

	do(LFront(l))

	LForEach(LRest(l), do)
}

func LMapGet(l List, key string) (string, bool) {
	if LEmpty(l) {
		return "", false
	}

	if k, v := LFront(l); k == key {
		return v, true
	}

	return LMapGet(LRest(l), key)
}

func LMapSet(l List, key, value string) List {
	if LEmpty(l) {
		return LAdd(NewList(), key, value)
	}

	if k, v := LFront(l); k == key {
		return LAdd(LRest(l), key, value)
	} else {
		return LAdd(LMapSet(LRest(l), key, value), k, v)
	}
}

func LMapDel(l List, key string) List {
	if LEmpty(l) {
		return l
	}

	if k, v := LFront(l); k == key {
		return LRest(l)
	} else {
		return LAdd(LMapDel(LRest(l), key), k, v)
	}
}

list_test.go

package mymap

import (
	"fmt"
	"testing"

	"github.com/stretchr/testify/require"
)

func TestList(t *testing.T) {
	l := NewList()

	require.True(t, LEmpty(l))

	l = LAdd(l, "foo", "bar")
	k, v := LFront(l)

	require.Equal(t, k, "foo")
	require.Equal(t, v, "bar")

	l = LAdd(l, "baz", "qux")
	k, v = LFront(l)

	require.Equal(t, k, "baz")
	require.Equal(t, v, "qux")

	l = LRest(l)
	k, v = LFront(l)

	require.Equal(t, k, "foo")
	require.Equal(t, v, "bar")
}

func TestLMap(t *testing.T) {
	l := NewList()
	printer := func(k, v string) {
		fmt.Printf("[%s] -> [%s]\n", k, v)
	}

	fmt.Println("1")
	l = LMapSet(l, "foo", "bar")
	LForEach(l, printer)

	fmt.Println("2")
	l = LMapSet(l, "baz", "qux")
	LForEach(l, printer)

	fmt.Println("3")
	l = LMapSet(l, "foo", "notbar")
	LForEach(l, printer)

	v, ok := LMapGet(l, "foo")
	require.True(t, ok)
	require.Equal(t, v, "notbar")

	v, ok = LMapGet(l, "baz")
	require.True(t, ok)
	require.Equal(t, v, "qux")

	v, ok = LMapGet(l, "notinthere")
	require.False(t, ok)

	l = LMapDel(l, "baz")
	v, ok = LMapGet(l, "baz")
	require.False(t, ok)
}

tree.go

package mymap

type BTree func() (leafFunc, valueFunc, leftFunc, rightFunc)

type leafFunc func() bool
type valueFunc func() (string, string)
type leftFunc func() BTree
type rightFunc func() BTree

func TNewLeaf() BTree {
	leaf := func() bool {
		return true
	}

	value := func() (string, string) {
		panic("value of leaf tree!")
	}

	left := func() BTree {
		panic("left of leaf tree!")
	}

	right := func() BTree {
		panic("right of leaf tree!")
	}

	return BTree(func() (leafFunc, valueFunc, leftFunc, rightFunc) {
		return leafFunc(leaf), valueFunc(value), leftFunc(left), rightFunc(right)
	})
}

func TJoin(k, v string, lt BTree, rt BTree) BTree {
	leaf := func() bool {
		return false
	}

	value := func() (string, string) {
		return k, v
	}

	left := func() BTree {
		return lt
	}

	right := func() BTree {
		return rt
	}

	return BTree(func() (leafFunc, valueFunc, leftFunc, rightFunc) {
		return leafFunc(leaf), valueFunc(value), leftFunc(left), rightFunc(right)
	})
}

func TLeaf(t BTree) bool {
	leaf, _, _, _ := t()
	return leaf()
}

func TValue(t BTree) (string, string) {
	_, value, _, _ := t()
	return value()
}

func TLeft(t BTree) BTree {
	_, _, left, _ := t()
	return left()
}

func TRight(t BTree) BTree {
	_, _, _, right := t()
	return right()
}

func TForEach(t BTree, do func(string, string)) {
	if TLeaf(t) {
		return
	}

	TForEach(TLeft(t), do)
	do(TValue(t))
	TForEach(TRight(t), do)
}

func TMapGet(t BTree, key string) (string, bool) {
	if TLeaf(t) {
		return "", false
	}

	k, v := TValue(t)
	if k == key {
		return v, true
	} else if k < key {
		return TMapGet(TLeft(t), key)
	} else {
		return TMapGet(TRight(t), key)
	}
}

func TMapSet(t BTree, key, value string) BTree {
	if TLeaf(t) {
		return TJoin(key, value, TNewLeaf(), TNewLeaf())
	}

	k, v := TValue(t)
	if k == key {
		return TJoin(key, value, TLeft(t), TRight(t))
	} else if k < key {
		return TJoin(k, v, TMapSet(TLeft(t), key, value), TRight(t))
	} else {
		return TJoin(k, v, TLeft(t), TMapSet(TRight(t), key, value))
	}
}

func TMapDel(t BTree, key string) BTree {
	newt := TNewLeaf()

	TForEach(t, func(k, v string) {
		if k != key {
			newt = TMapSet(newt, k, v)
		}
	})

	return newt
}

tree_test.go

package mymap

import (
	"fmt"
	"testing"

	"github.com/stretchr/testify/require"
)

func TestTMap(t *testing.T) {
	bt := TNewLeaf()
	printer := func(k, v string) {
		fmt.Printf("[%s] -> [%s]\n", k, v)
	}

	fmt.Println("1")
	bt = TMapSet(bt, "foo", "bar")
	TForEach(bt, printer)

	fmt.Println("2")
	bt = TMapSet(bt, "baz", "qux")
	TForEach(bt, printer)

	fmt.Println("3")
	bt = TMapSet(bt, "foo", "notbar")
	TForEach(bt, printer)

	v, ok := TMapGet(bt, "foo")
	require.True(t, ok)
	require.Equal(t, v, "notbar")

	v, ok = TMapGet(bt, "baz")
	require.True(t, ok)
	require.Equal(t, v, "qux")

	v, ok = TMapGet(bt, "notinthere")
	require.False(t, ok)

	bt = TMapDel(bt, "baz")
	v, ok = TMapGet(bt, "baz")
	require.False(t, ok)
}