On 02/23/2011 03:28 AM, bearophile wrote:
A task from the RosettaCode site asks to generate a Sierpinski carpet like this, on given order:########################### # ## ## ## ## ## ## ## ## # ########################### ### ###### ###### ### # # # ## # # ## # # # ### ###### ###### ### ########################### # ## ## ## ## ## ## ## ## # ########################### ######### ######### # ## ## # # ## ## # ######### ######### ### ### ### ### # # # # # # # # ### ### ### ### ######### ######### # ## ## # # ## ## # ######### ######### ########################### # ## ## ## ## ## ## ## ## # ########################### ### ###### ###### ### # # # ## # # ## # # # ### ###### ###### ### ########################### # ## ## ## ## ## ## ## ## # ########################### This is a Scala implementation of a function that prints the carpet: def nextCarpet(carpet: List[String]): List[String] = ( carpet.map(x => x + x + x) ::: carpet.map(x => x + x.replace('#', ' ') + x) ::: carpet.map(x => x + x + x)) def sierpinskiCarpets(n: Int) = (Iterator.iterate(List("#"))(nextCarpet) drop n next) foreach println A D version that uses arrays: import std.stdio, std.string, std.algorithm, std.array, std.range; string[] nextCarpet(string[] c) { auto b = array(map!q{a ~ a ~ a}(c)); return b ~ array(map!q{a ~ a.replace("#"," ") ~ a}(c)) ~ b; } void main() { auto c = recurrence!((a, n){ return nextCarpet(a[n-1]); })(["#"]); writeln(array(take(c, 4)).back.join("\n")); } Few notes: - I don't know how to take just the 4th item of a lazy sequence. array(take(c, 4)).back is not good. - recurrence() is a bit overkill. A function like iterate() simplifies the code: auto c = iterate!nextCarpet(["#"], 4); - I don't see a simple way to create a lazy nextCarpet(), without those array(). The seed (["#"]) can't be an array, but even wrapping it with a lazy map!q{a}(["#"]) solves nothing. chain(map(chain...))) are all different types, so I think it can't work. The types in that Scala code are sound because it uses a lazy list type, that supports the ::: operator for concatenation, and List("#") to create the correctly typed seed. That carpet.map() returns a List[String]. So both the input and output of the Scala nextCarpet() are of the same type, List[String]. So such lazy list type template becomes really useful if you want to program in a lazy functional style.
Maybe we should reverse the point of view and start with Range. A base type for anything 'sequential' (iterable) is Range of E (element type). Then, an array E[] is a Range of E that just happens to have its elements pre-stored. Ditto for any other collection. And a slice, or any other kind of 'view' into a collection, is a Range of E that just happens to have direct access to its elements (in memory, via pointer; or via cursor, or whatever).
Denis -- _________________ vita es estrany spir.wikidot.com
