「LISPにはscanlに該当する関数ってあるんでしょうか？」

指名ktkr!!力不足ですが、せっかくですので。

• Haskellのscanl関数でフィボナッチ。 - このブログは証明できない。

ところで、LISPにはscanlに該当する関数ってあるんでしょうか？ > valvallowさん

正直わかりません、知りません、すみません。。Haskell 読めませんが、fold っぽいですね。取りあえず確認がてら同じようなものをでっち上げてみます。遅延評価でもなく Gauche 依存ですけれども。以下コード。

	;; Prelude> scanl (+) 0 []
	;; [0]
	;; Prelude> scanl (+) 0 [1]
	;; [0,1]
	;; Prelude> scanl (+) 0 [1,2]
	;; [0,1,3]
	;; Prelude> scanl (+) 0 [1..10]
	;; [0,1,3,6,10,15,21,28,36,45,55]
	;; (scanl + 0 '())
	;; (0)
	;; (scanl + 0 '(1))
	;; (0 1)
	;; (scanl + 0 '(1 2))
	;; (0 1 3)
	;; (scanl + 0 (iota 10 1))
	;; (0 1 3 6 10 15 21 28 36 45 55)
	(use srfi-1)
	(use srfi-8)
	(use gauche.collection)
	(define (scanl proc seed ls)
	(receive (n l)
	(fold2 (lambda (ele acc-n acc-l)
	(let1 n (proc ele acc-n)
	(values n (cons n acc-l))))
	seed (cons seed '()) ls)
	(reverse l)))
	(scanl + 0 '())
	;; (0)
	(scanl + 0 '(1))
	;; (0 1)
	(scanl + 0 '(1 2))
	;; (0 1 3)
	(scanl + 0 (iota 10 1))
	;; (0 1 3 6 10 15 21 28 36 45 55)

view raw scanl.scm hosted with ❤ by GitHub

非常にカッコ悪いですね・・・。なんでこんなに難しそうになるわけ・・・。


素直に named-let で書いた方がよかったみたいです。

	(define (scanl p s ls)
	(let rec ((ls (cons s ls))(accn s)(accl '()))
	(if (null? ls)
	(reverse accl)
	(let1 n (p (car ls) accn)
	(rec (cdr ls) n (cons n accl))))))
	(scanl + 0 '())
	;; (0)
	(scanl + 0 '(1))
	;; (0 1)
	(scanl + 0 '(1 2))
	;; (0 1 3)
	(scanl + 0 (iota 10 1))
	;; (0 1 3 6 10 15 21 28 36 45 55)

view raw scanl2.scm hosted with ❤ by GitHub

きっと R5RS の範囲の Scheme にはないんじゃないでしょうか。たぶん R6RS にも。srfi か Common Lisp にはあるかも？教えてエロい人！

追記

そうか。fold2 で書くにしても、こうすれば receive 取れて少しマシか。

	(use srfi-1)
	(use srfi-8)
	(use gauche.collection)
	(define (scanl proc seed ls)
	(reverse
	(fold2 (lambda (ele acc-l acc-n)
	(let1 n (proc ele acc-n)
	(values (cons n acc-l) n)))
	(cons seed '()) seed ls)))
	(scanl + 0 '())
	;; (0)
	(scanl + 0 '(1))
	;; (0 1)
	(scanl + 0 '(1 2))
	;; (0 1 3)
	(scanl + 0 (iota 10 1))
	;; (0 1 3 6 10 15 21 28 36 45 55)

view raw scanl3.scm hosted with ❤ by GitHub

追記2

毎度のことながら教えていただきました！

• Twitter / SaitoAtsushi: @valvallow (use gauche.col ...

@valvallow (use gauche.collection)(define (scanl f x xs)(values-ref (map-accum (^(a acc)(let1 z (f a acc) (values z z))) x xs) 0))

なるほど、map-accum ですかー！ちょっと写経。

	;; https://twitter.com/SaitoAtsushi/statuses/20302777187
	(use gauche.collection)
	(define (scanl f s ls)
	(values-ref (map-accum (lambda (e acc)
	(let1 n (f e acc)
	(values n n))) s (cons s ls)) 0))
	(scanl + 0 '())
	;; (0)
	(scanl + 0 '(1))
	;; (0 1)
	(scanl + 0 '(1 2))
	;; (0 1 3)
	(scanl + 0 (iota 10 1))
	;; (0 1 3 6 10 15 21 28 36 45 55)

view raw scanl4.scm hosted with ❤ by GitHub

values-ref ってのもあるのか。

• Gauche ユーザリファレンス: 9.3 gauche.collection - コレクションフレームワーク
• map-accum - Gauche ユーザリファレンス: 9.3 gauche.collection - コレクションフレームワーク
• values-ref - Gauche ユーザリファレンス: 6.16 制御
• fold2 - Gauche ユーザリファレンス: 9.3 gauche.collection - コレクションフレームワーク
• receive - Gauche ユーザリファレンス: 4.6 変数束縛

追記3

Clojure で書いてる人がいらっしゃる。

• Clojureでscanl - maoeのブログ

追記4

遅延評価だとこんな感じ？いや、良くわかりませんが・・・。

	(use util.stream)
	(define (scanl p s ls)
	(let rec ((ls (stream-cons s (list->stream ls)))
	(accn s)
	(accl (list->stream '())))
	(if (stream-null? ls)
	(stream-reverse accl)
	(let1 n (p (stream-car ls) accn)
	(rec (stream-cdr ls) n (stream-cons n accl))))))
	(stream->list (stream-take (scanl + 0 '()) 1))
	;; (0)
	(stream->list (stream-take (scanl + 0 '(1)) 2))
	;; (0 1)
	(stream->list (stream-take (scanl + 0 '(1 2)) 3))
	;; (0 1 3)
	(stream->list (stream-take-while (pa$ > 1000)
	(scanl + 0 (iota 1000 1))))
	;; (0 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210 231 253 276 300 325 351 378 406 435 465 496 528 561 595 630 666 703 741 780 820 861 903 946 990)
	(stream->list (stream-filter (lambda (n)
	(and (< 5000 n)
	(< n 10000)))
	(scanl + 0 (iota 10000 1))))
	;; (5050 5151 5253 5356 5460 5565 5671 5778 5886 5995 6105 6216 6328 6441 6555 6670 6786 6903 7021 7140 7260 7381 7503 7626 7750 7875 8001 8128 8256 8385 8515 8646 8778 8911 9045 9180 9316 9453 9591 9730 9870)

view raw scanl5.scm hosted with ❤ by GitHub

• Gauche ユーザリファレンス: 11.53 util.stream - ストリームライブラリ

追記5

また教えていただきました！ですが、マニュアル見ても iterator->stream がよくわかりません。。

• @valvallow (use srfi-1)(use util.stream)(define(scanl f x xs)(iterator->stream(lambda(n e)(until(null? xs)(n x)(set! x(f x(pop! xs))))(e))))

@valvallow (use srfi-1)(use util.stream)(define(scanl f x xs)(iterator->stream(lambda(n e)(until(null? xs)(n x)(set! x(f x(pop! xs))))(e))))

せっかくなので、インデント付けて gist に貼っつけました。

	;; @valvallow (use srfi-1)(use util.stream)(define(scanl f x xs)(iterator->stream(lambda(n e)(until(null? xs)(n x)(set! x(f x(pop! xs))))(e)))) - https://twitter.com/SaitoAtsushi/statuses/20372687335
	(use srfi-1)
	(use util.stream)
	(define (scanl f x xs)
	(iterator->stream (lambda (n e)
	(until (null? xs)
	(n x)
	(set! x (f x (pop! xs))))
	(e))))

view raw scanl6.scm hosted with ❤ by GitHub