lazyなGoやリスト演算なGoについて

こんにちは。ゆるふわGoクソ野郎の@MasashiSalvador57fです。
Go Advent Calendar 2015 12/2の投稿を忘れていたので投稿します。
真新しい話題ではないかもしれませんが、
関数型っぽい書き方をGoでする方法について書いていきます。

結論からいうとあまりうまく行きません...

大体のモダンな言語だとmapやらなにやらって実装されてますけど、
goはsimpleさを追求しているせいかそういうのが標準では入っていないですよね。
mapとzipをかやっぱり便利だし、その考え方に慣れると他のやり方がだるかったりします。

Table of Contents

• リスト演算のライブラリ
  • userscore.go
  • itertools.go
  • 各ライブラリ深追い
• 遅延評価？ in Go

リスト演算のライブラリ(1) underscore.go

公式サイト(ちょっとかっこいい）
http://tobyhede.github.io/go-underscore/

This package is in heavy flux at the moment as I work to incorporate feedback from various sources
## いろんなとこのフィードバックガッチャンコしてるから、このパッケージ結構流動的だぜ!

微妙に不安なWARNINGが書いてありますね

インストール

go get github.com/tobyhede/go-underscore #お馴染みの go get

このライブラリ、READMEがくっそ適当や...

Map

READMEに載ってるサンプルコードの引き数の順番がおかしくて変なエラーが出ました
そのおかげでソースコード読むきっかけになりました。それは後ほど

import (
	"fmt"

	"github.com/tobyhede/go-underscore"
)

// _.filterみたいに_がGoだと使えないっぽいですね
// _だと値を捨てることになるので
func main() {
	is := []int{1, 2, 3, 4, 5}

	// Mapは interface{} -> interface{}に対応しているので
	// そんな感じに書かないといけない使いづらい...
	double := func(i interface{}) interface{} {
		return i.(int) * 2
	}
	m := un.Map(double, is)
	fmt.Println(m) # [2,4,6,8,10]
	
	//各型に対するMapは定義できる
	double2 := func(i int) int {
		return i * 2
	}

	m2 := un.MapInt(double2, is)
	fmt.Println(m2) # [2,4,6,8,10]
}

型に対するMapを生成するhelperは付属しているのでMapXXXみたいな関数をよしなに定義できる
(使いのか問題はもちろんある)

package main

import (
	"fmt"

	"github.com/davecgh/go-spew/spew"
	"github.com/tobyhede/go-underscore"
)

// 適当なstruct
type HogeInt struct {
	a int
	b int
}

// _.filterみたいに_がGoだと使えないっぽいですね
// _だと値を捨てることになるので
func main() {
	s := []string{"a", "b", "c", "d"}
	var SMap func(func(string) string, []string) []string
	un.MakeMap(&SMap)

	fn := func(s string) string {
		return s + "!"
	}

	m := SMap(fn, s)
	fmt.Println(m)

	var HIMap func(func(HogeInt) HogeInt, []HogeInt) []HogeInt
	un.MakeMap(&HIMap)

	var h1, h2, h3 HogeInt

	h1.a = 1
	h1.b = 2
	h2.a = 1
	h2.b = 2
	h3.a = 3
	h3.b = 4

	his := []HogeInt{h1, h2, h3}
	double := func(a HogeInt) HogeInt {
		var hi HogeInt
		hi.a = a.a * 2
		hi.b = a.b * 2
		return hi
	}

	his2 := HIMap(double, his)
	spew.Dump(his2)
}

Each

package main

import (
	"fmt"

	"github.com/tobyhede/go-underscore"
)

func main() {
	var EachInt func(func(value, i int), []int)
	un.MakeEach(&EachInt)
	var sum int

	fn := func(v, i int) {
		sum += v
	}

	i := []int{1, 2, 3, 4, 5}
	EachInt(fn, i)

	fmt.Printf("%#v\n", sum)
}

雑感

使いづらい...orz

リスト演算のライブラリ(2) itertools.go

さっき使いづらかったのでこっちには期待...
こっちは最終更新が2years agoとかですね

これとは別に
http://doloopwhile.hatenablog.com/entry/2014/05/26/020907
こんな記事もありました。

インストール

go get github.com/yanatan16/itertools

ベンチマーク的には遅い / 実験的だよとのこと
こちらはgodocもあるしgo-underscoreよりマシな気がする。
使えるか/使うかは別問題ですが

Map / Reduce

package main

import (
	"fmt"

	"github.com/yanatan16/itertools"
)

func main() {
	k := itertools.New(1, 2, 3, 4, 5, 6)
	// NewするとIterが作られる（実態はチャンネル）

	double := func(i interface{}) interface{} {
		return i.(int) * 2
	}
	add := func(i1, i2 interface{}) interface{} {
		return i1.(int) + i2.(int)
	}
	k = itertools.Map(double, k)

	s := itertools.Reduce(k, add, 0)
	fmt.Println(s)
}

Filter

	isOdd := func(i interface{}) bool {
		return i.(int)%2 == 1
	}
	d := itertools.Filter(isOdd, itertools.New(1, 2, 3, 1, 2, 3, 11))
	spew.Dump(itertools.List(d))

普通に使うことはできそう（使い所問題は棚上げ）
List演算に使いたい関数が
interface {} -> interface{}でなとダメなのも非常につらい。
いい感じのsliceに対する関数欲しいなぁ...

各ライブラリ深追い

underscore.go

Mapの定義

// シンプル~
var Map func(interface{}, interface{}) []interface{}

func init() {
	MakeMap(&Map) //ここでMap関数作ってる
	MakeMap(&MapString)
	MakeMap(&MapInt)
	MakePMap(&MapP)
	MakePMap(&MapPString)
	// MakeMap(&MapStringToBool)
}

// MakeMap implements a typed Map function in the form Map func(func(A) C, []A) []C
func MakeMap(fn interface{}) {
	Maker(fn, mapImpl)
}

Makerで関数を作っているらしい。ということでunderscore.goというファイルのMaker関数へ
// Maker takes a function pointer (fn) and implements it with the given
// reflection-based function implementation
// Internally uses reflect.MakeFunc

func Maker(fn interface{}, impl func(args []reflect.Value) (results []reflect.Value)) {
	fnV := reflect.ValueOf(fn).Elem()
	fnI := reflect.MakeFunc(fnV.Type(), impl)
	fnV.Set(fnI)
}

itertools.go

//Newで作ってるイテレータの実態はchannel
type Iter chan interface{}

チャンネルから取り出して詰めて返すみたいな実装ですね。

func Filter(pred Predicate, it Iter) Iter {
	c := make(Iter)
	go func () {
		for el := range it {
			if keep := pred(el); keep {
				c <- el
			}
		}
		close(c)
	}()
	return c
}

そのたsyncとかatomicパッケージも調べることになり勉強になりました

遅延評価inGO

1回評価したらメモ化けしておくという非常にゆるい意味でのlazy evaluationは何人か実装にトライしている方がいるようです。Goの言語仕様的に実用に耐えそうなイメージは全く無いですね.

https://github.com/Merovius/go-misc/blob/master/lazy/lazy.go
https://godoc.org/bitbucket.org/weberc2/lazy

辺りが実装のようです。

前者の実装を見てみると、

type lazyByte struct {
	v byte
	f func() byte
	m sync.Mutex
	o uint32
}

func (v *lazyByte) Get() byte {
	if atomic.LoadUint32(&v.o) == 1 {
		return v.v
	}

	v.m.Lock()
	defer v.m.Unlock()

	if v.o == 0 {
		v.v = v.f()
		v.o = 1
		v.f = nil
	}
	return v.v
}

と、sync.Mutexで適当にロックをとって、一度評価された後はすでに評価されている値を返すような実装になっていました。merovious/go-misc/lazyの実装は確かにImmutableで一度評価されると再評価時にはメモ化けされているという条件を満たしています。
↑のような実装は一度だけ評価する/評価するたびに結果が変わらない関数を実装するのに使えそう...

一応遅延評価ということで、フィボナッチ数をゴニョるサンプルコードを書いてみましたが、
goの末尾再帰の仕組み的にもこれでは評価できなさそう。
そもそも関数つくる部分のコストはそれなりにありそう(憶測)なので、このやり方であえて遅延評価の仕組みを入れるメリットは殆ど無いなぁ...

package main

import (
	"fmt"

	"merovius.de/go-misc/lazy"
)

type lazyInt func() int

func fib(n lazyInt) int {
	if n() < 2 {
		return n()
	}

	return fib(lazy.Int(func() int {
		return n() - 2
	})) + fib(lazy.Int(func() int {
		return n() - 1
	}))
}

func fib2(n lazyInt) lazyInt {
	if n() < 2 {
		return n
	}

	return lazy.Int(func() int {
		return fib(lazy.Int(func() int {
			return n() - 2
		})) + fib(lazy.Int(func() int {
			return n() - 1
		}))
	})
}

func main() {
	x := lazyInt(func() int {
		return 40
	})

	fmt.Println(fib2(x)())
	fmt.Println(fib(x))
}