What is the most interesting line of code you have written?

Answer on @Quora by Vladislav Zorov to What is the most interesting line of code you have written?  Some background: Lisp uses singly-linked lists –  cons  constructs a pair from two values; for a list, the "head" is the value you want to store, while the "tail" is the rest of the list. To make the tail, the function just calls itself recursively (but makes sure all children end up as a single list, not a list-of-lists; apply  works in the same way as in JavaScript, i.e. allows you to call a function that expects multiple arguments with a list instead).  Just for fun, here's an iterator-based version in Python 3: 1def flatten(node): 2    yield node.value 3    for child in node.children: 4        yield from flatten(child)

Answer by Vladislav Zorov:

I don't normally write interesting lines; if a line is interesting, it should be refactored ­čśÇ

But, specially for this answer:

(define (flatten n)
  (cons (node-value n) (apply append (map flatten (node-children n)))))

Given:

#lang racket

(struct node (value children))

(define tree
  (node
   'root
   (list
    (node 'child_1 (list (node 'child_1_1 '())))
    (node 'child_2 '())
    (node 'child_3 (list (node 'child_3_1 '()))))))

…it produces:

> (flatten tree)
'(root child_1 child_1_1 child_2 child_3 child_3_1)

A list version of the tree, from a pre-order traversal ­čÖé

But, even here, this

(apply append (map ... ))

is an instance of something more general; namely

flatmap

:

(define (flatmap proc lst)
  (apply append (map proc lst)))

(define (flatten n)
  (cons (node-value n) (flatmap flatten (node-children n))))

Some background: Lisp uses singly-linked lists –

cons

constructs a pair from two values; for a list, the "head" is the value you want to store, while the "tail" is the rest of the list. To make the tail, the function just calls itself recursively (but makes sure all children end up as a single list, not a list-of-lists;

apply

works in the same way as in JavaScript, i.e. allows you to call a function that expects multiple arguments with a list instead).

Just for fun, here's an iterator-based version in Python 3:

def flatten(node):
    yield node.value
    for child in node.children:
        yield from flatten(child)

You can take elements one by one:

>>> g = flatten(tree)
>>> next(g)
'root'
>>> next(g)
'child_1'
>>> next(g)
'child_1_1'
>>> next(g)
'child_2'

…or build a list (the

list

constructor will eat anything iterable):

>>> list(flatten(tree))
['root', 'child_1', 'child_1_1', 'child_2', 'child_3', 'child_3_1']

If you want this streaming behavior in Racket, you can either change the

cons

to

stream-cons

and

append

to

stream-append

, or change

#lang racket

to

#lang lazy

and everything starts streaming by default (because in languages with lazy evaluation, nothing is evaluated until you need it).

What is the most interesting line of code you have written?

Advertisements

Leave a comment

Filed under Life

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s