Logo, Ruby & JavaScript

I’ve been teaching my eldest daughter to program in Logo over the summer. Brian Harvey has posted PDF files for a set of excellent books on learning to program in Logo on his web site. The Berkeley version of Logo he’s produced is really excellent. It’s not just your typical turtle graphics language; it has arrays, macros, file processing, graphics, etc.

While perusing his site, I came across a tiny Logo program that demonstrates a little of its power. I was curious what it would look like in Ruby, so I ported it, then I had to see what it looked like in JavaScript.

If anyone wants to add other languages, that would be great!

See the sample page for example output.

Logo

1
2
3
4

to choices :menu [:sofar []]
  if emptyp :menu [print :sofar stop]
  foreach first :menu [(choices butfirst :menu sentence :sofar ?)]
end

choices [[small medium large]
  [vanilla [ultra chocolate] lychee [rum raisin] ginger]
  [cone cup]]

UPDATE 9/2/07: Got an even more concise solution from Brian Harvey:

1
2
3

to choices :menu
   foreach crossmap "sentence :menu "print
end

Ruby

1
2
3
4
5

def choices menu, sofar=[]
  if menu.empty?: puts sofar.join(' ')
  else menu[0].each {|item| choices(menu[1..-1],
    sofar + [item]) } end
end

choices [['small', 'medium', 'large'],
  ['vanilla', 'ultra chocolate', 'lychee', 'rum raisin', 'ginger'],
  ['cone', 'cup']]

JavaScript

1
2
3
4
5
6

function choices(menu, sofar) {
  if (emptyp(menu)) print(sofar);
  else foreach(menu[0],
   function (x) {
    choices(menu.slice(1), sofar.concat(x)); });
}

choices([['small', 'medium', 'large'],
  ['vanilla', 'ultra chocolate', 'lychee', 'rum raisin','ginger'],
  ['cone', 'cup']], []);

I had to create a few helpers for the JavaScript version:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

function emptyp(a) {
  return a.length === 0;
}
function print(list) {
  foreach(list, function (x) { document.write(x + ' '); });
  document.write('<br />');
}
function foreach(arr, f) {
  for (var idx in arr) { f(arr[idx]); }
}

Comments from my old blog

Jordan L. Aug 31, 2007

Jordan L. contributed this Java version (I added class wrapper and normalized choice strings).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import java.util.*;

public class Choices {
  public static void choices(List<Object[]> choices, String sofar) {
    if (choices.isEmpty())
      System.out.println(sofar);
    else
      for (Object choice : choices.get(0))
        choices(choices.subList(1, choices.size()),
          sofar + choice.toString() + " ");
  }

  public static void main(String[] args) {
    choices(Arrays.asList(new Object[][] {
      { "small", "medium", "large" },
      { "vanilla", "ultra chocolate", "lychee", "rum raisin", "ginger" },
      { "cup", "cone" } }), "");
  }
}

Sam N. Sep 1, 2007

Here’s a Scheme version from a friend in Ohio that I tweaked just a bit.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

(define (choices menu sofar)
  (cond
    [(null? menu)
      (for-each (lambda (word) (printf "~a " word)) sofar)
      (newline)]
    [else
      (for-each (lambda (item)
        (choices
          (cdr menu)
          (append sofar (list item)))) (car menu))]))

(choices (list
  '(small medium large)
  '(vanilla "ultra chocolate" lychee "rum raisin" ginger)
  '(cone cup)) '())

Brian Adkins Sep 1, 2007

Here’s a Common Lisp version, but I’m hoping some kind soul on comp.lang.lisp will provide me with pointers to make it cleaner. Especially with the print-choice function.

1
2
3
4
5
6
7
8
9

(defun print-choice (lst)
  (dolist (i lst) (format t "~a " i))
  (format t "~%"))

(defun choices (menu sofar)
  (if menu
    (dolist (i (car menu))
      (choices (cdr menu) (append sofar (list i))))
    (print-choice sofar)))

(choices (list
  (list "small" "medium" "large")
  (list "vanilla" "ultra chocolate" "lychee" "rum raisin" "ginger")
  (list "cone" "cup")) '())

Luke Sep 1, 2007

PHP:

1
2
3
4
5
6
7

function choices($menu, $sofar) {
    if (count($menu))
        foreach ($menu[0] as $item)
            choices(array_slice($menu,1), $sofar."$item ");
    else
        echo "$sofar\n";
}

choices(array(
    array("small","medium","large"),
    array("vanilla","ultra chocolate","lychee","rum rasin","ginger"),
    array("cone","cup")), "");

Chip H. Sep 1, 2007

OK, here’s a C# version. No need for a namespace declaration if we’re OK running in the default namespace. No need for a using statement either, if you fully qualify your types.

Chip H.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Program
{
  static void Main(string[] args) {
    string[] sizes = new string[] { "small ", "medium ", "large " };
    string[] flavors = new string[] { "vanilla ", "ultra chocolate ", "lychee ", "rum raisin ", "ginger " };
    string[] servings = new string[] { "cone", "cup" };

    foreach (string size in sizes)
      foreach (string flavor in flavors)
        foreach (string serving in servings)
          System.Console.WriteLine(size + flavor + serving);
  }
}

Scott Moonen Sep 1, 2007

Since it would be trivial to translate the Ruby version directly to Python, I thought I’d approach the problem from a completely different angle. Here’s my 4-line Python version:

1
2
3
4

optstr  = lambda x : (type(x)==str)*str(x)+(type(x)!=str)*' '.join(x)
prod1   = lambda elem, vec : map(lambda x : optstr(elem)+' '+optstr(x), vec)
xprod   = lambda vec1, vec2 : reduce(list.__add__,map(lambda elem : prod1(elem ,vec2), vec1))
choices = lambda x : '\n'.join(reduce(xprod, x))

q = [['small','medium','large'],
  ['vanilla', ['ultra', 'chocolate'], 'lychee', ['rum', 'raisin'], 'ginger'],
  ['cone', 'cup']]

print choices(q)

Brian Adkins Sep 1, 2007

Here’s a direct translation of Scott’s Python solution to Ruby. I had to write the reduce function because I wasn’t aware of any built-in Ruby function that was close.

I like the Python lambda invocation better than having to say x.call() in Ruby.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def reduce fn, lst
  return lst if lst.length < 2
  result = fn.call(lst[0],lst[1])
  return lst.length == 2 ? result : reduce(fn, [fn.call(lst[0],lst[1])] + lst[2..-1])
end

optstr  = lambda {|x| x.instance_of?(String) ? x : x.join(' ')}
prod1   = lambda {|elem, vec| vec.map {|x| optstr.call(elem)+' '+optstr.call(x)}}
xprod   = lambda {|vec1, vec2| reduce(lambda {|a, b| a+b}, vec1.map {|elem| prod1.call(elem, vec2)})}
choices = lambda {|x| reduce(xprod, x).join("\n")}

q = [ ['small','large'],
 ['vanilla', ['ultra', 'chocolate'], ['rum', 'raisin']],
 ['cone', 'cup'],
 [ 'here', 'to go'] ]

puts choices.call(q)

Brian Adkins Sep 2, 2007

Lisp translation of Scott’s Python translation of the Logo program 🙂

Had to write a join-string function since I couldn’t find a Lisp equivalent of Ruby’s list.join(‘ ‘) or Python’s ‘ ‘.join(list)

I’m very much a Lisp newbie, but I was surprised how straightforward the port went (except for getting stuck on join-string and having to research to find #Newline – argh). I’m curious, given a large set of algorithms, whether it would be easier to port Python/Ruby to Lisp or vice versa given equal language skills.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

;; Helper function
(defun join-string (sep lst)
  (if (cdr lst)
    (concatenate 'string (car lst) (string sep) (join-string sep (cdr lst)))
    (car lst)))

(defun prod1 (elem vec)
  (mapcar #'(lambda (x) (join-string " " (list elem x))) vec))

(defun xprod (vec1 vec2)
  (reduce
    #'(lambda (a b) (concatenate 'list a b))
    (mapcar #'(lambda (elem) (prod1 elem vec2)) vec1)))

(defun choices (x)
  (join-string #\Newline (reduce #'xprod x)))

(princ (choices (list (list "small" "large")
            (list "vanilla" "ultra chocolate")
            (list "cone" "cup")
            (list "to go" "eat in"))))

Ben Rogers Sep 2, 2007

My first instinct in python turns the cross product function inside out which may not optimize as well. Shame, because it feels a lot more readable to me.

1
2
3
4
5
6
7
8

def cross(aa):
    if len(aa) == 0:
        return [()]
    else:
        return sum([[(x,) + y for x in aa[0]] for y in cross(aa[1:])], [])

def choices(menu):
    return "\n".join(" ".join(x) for x in cross(menu))

print choices([['small',  'medium',  'large'],
         ["vanilla","ultra chocolate","lychee","rum rasin","ginger"],
         ['cup', 'cone']])

Ben Rogers Sep 3, 2007

Please forgive my amature Haskell. I don’t know whether there is a cross product function in one of its libraries, but writing one isn’t too hard.

1
2

choices (xs:[]) = xs
choices (xs:xss) = foldr ((++) . (\ys -> map (++ " " ++ ys) xs)) [] (choices xss)

main = putStr (unlines(
       choices [["small",  "medium",  "large"],
                ["vanilla","ultra chocolate","lychee","rum rasin","ginger"],
                ["cup", "cone"]]
                      ))

Note from Brian: this didn’t seem to work with hugs, so I used ghc with no problems. 1) save code to choices.hs, 2) ghc choices.hs, 3) ./a.out

Brian Adkins Sep 4, 2007

Got a helpful response on comp.lang.lisp that replaced my print-choice function with a simple format. I’m really liking Common Lisp:

1
2
3
4
5

(defun choices (menu &optional (sofar '()))
  (if menu
    (dolist (i (car menu))
      (choices (cdr menu) (append sofar (list i))))
    (format t "~{~a~^ ~}~%" sofar)))

(choices (list
           (list "small" "medium" "large")
           (list "vanilla" "ultra chocolate" "lychee" "rum raisin" "ginger")
           (list "cone" "cup")))

mt Sep 5, 2007

Prolog:

1
2
3

choices([[small, medium, large],
[vanilla, ‘ultra chocolate’, lychee, ‘rum raisin’, ginger],
[cone, cup]]).

Example query:

`?- choices(Cs), maplist(member, C, Cs), maplist(format(“~w “), C), nl, fail.
small vanilla cone
small vanilla cup
small ultra chocolate cone
etc.

PL Sep 6, 2007

A Smalltalk version.

“First, a new subclass called Counter was constructed from the Array class. Two variables were added to the class: slave and value. The following methods were added.”

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

initialize
  slave := nil. value := 1. ^self

increment
  value := value + 1.
  value > self size
    ifTrue:
      [value := 1.
      slave notNil ifTrue: [slave increment]]

last
  ^value = self size and: [slave isNil ifFalse: [slave last] ifTrue: [true]]

slave
  ^slave

slave: anObject
  slave := anObject

value
  Transcript show: (self at: value); show: ' '.
  slave notNil ifTrue: [slave value].
  ^value.

“The choices program.”

1
2
3
4
5
6
7
8

counter := Counter withAll: #('small' 'medium' 'large').
counter slave: (Counter withAll: #('vanilla' 'ultra chocolate' 'lychee' 'rum raisin' 'ginger')).
counter slave slave: (last := (Counter withAll: #('cone' 'cup'))).
[counter last] whileFalse:
	[x value.
	x increment.
	Transcript cr].
x value

Brian adkins Jan 31, 2008

Arc

1
2
3
4
5

(def choices (menu (o result '()))
  (if menu
    (each x (car menu)
      (choices (cdr menu) (join result (list x))))
    (prall result "n" " ")))

(choices '(
  ("small" "medium" "large")
  ("vanilla" "ultra chocolate" "lychee" "rum raisin" "ginger")
  ("cone" "cup")))

Ric Nov 10, 2008

There are some APL, J & K versions of this program in this comp.lang.apl thread. Here is a version in J:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Options=: ;: each ('small large medium');('ginger lychee rum_raisin ultra_choc vanilla');('cone cup')
choices=: monad : ';:^:_1 >,{ y'
choices Options
small vanilla cone
small vanilla cup
small ultra_choc cone
...
large rum_raisin cup
large ginger cone
large ginger cup

Scott Moonen Aug 17, 2009

Ha, well, turns out that the clojure-contrib library, a standard part of any serious Clojure setup, has some built-in combinatorics support. That brings the Clojure sample down to a simple call to “cartesian-product”. I use “apply” below since cartesian-product expects the choices to be supplied as a series of arguments rather than a list of lists.

1
2
3
4
5
6
7
8

(use 'clojure.contrib.combinatorics)

(def choices
  '(("small" "medium" "large")
    ("vanilla" "ultra chocolate" "lychee" "rum raisin" "ginger")
    ("cone" "cup")))

(doseq [x (apply cartesian-product choices)] (apply println x))

Brian Adkins Oct 13, 2011

I recently had a problem pop up where I needed to create a cartesian product of N lists. I’m coding it in Standard ML, so I now have a new entry in that language. Pretty concise I think:

1
2
3
4
5
6

fun cartesian ([x]) = map (fn e => [e]) x
  | cartesian (x::xs) =
    let val tailCross = cartesian xs
    in concat(map (fn e => map (fn e2 => e::e2) tailCross) x) end

fun choices xs = map join (cartesian xs)

The Standard ML REPL abbreviated the list, but it works fine:

- choices [["Small","Medium", "Large"],
           ["vanilla", "ultra chocolate", "lychee", "rum raisin", "ginger"],
           ["cone", "cup"]];
val it =
  ["Small vanilla cone","Small vanilla cup","Small ultra chocolate cone",
   "Small ultra chocolate cup","Small lychee cone","Small lychee cup",
   "Small rum raisin cone","Small rum raisin cup","Small ginger cone",
   "Small ginger cup","Medium vanilla cone","Medium vanilla cup",...]
  : string list

Brian Adkins Oct 16, 2011

Here’s a better cartesian using nested folds that’s about twice as fast as the concat / map version:

1
2
3
4
5
6
7

fun cartesian [] = []
  | cartesian ([x]) = map (fn e => [e]) x
  | cartesian (x::xs) =
    let val tailCross = cartesian xs
    in foldr (fn (x',result) =>
        foldr (fn (tc,l) => (x'::tc) :: l ) result tailCross) [] x
    end

Brian Adkins Aug 4, 2012

Two more Haskell versions:

1
2
3
4
5
6
7
8

cartesian []     = []
cartesian [x]    = [[e] | e <- x]
cartesian (x:xs) = [ x' : rest | x' <- x, rest <- cartesian xs ]
cartesian [] = []
cartesian [x] = map (e -> [e]) x
cartesian (x:xs) = foldr (x' result ->
                 (foldr (tc l -> (x':tc):l) result tailCross)) [] x
   where tailCross = cartesian xs

Brian Adkins Aug 24, 2018

Racket added cartesian-product in 6.3, so:

1
2

(define (choices menu)
  (apply cartesian-product menu))

(choices (list
          '(small medium large)
          '(vanilla "ultra chocolate" lychee "rum raisin" ginger)
          '(cone cup)))

I think we have a winner! :)