Unorthodox opinions on computer science and programming.
OK (interpreting 'descendants' as including the root).Incorrect solution (descendants = concatMap descendants . children): 20 secondsUnsuccessfully trying to look up the Racket equivalent of concatMap: 5 minutes (it's append-map, but I had to consult SRFI-1 to discover that)Deciding to stick with Haskell: 5 secondsDeciding to actually test it, and finding codepad (via Try Haskell): 1 minute and a painful admission of fallibilityImplementation, and fixing the bug: 3 minutesVacillating between different tree structures: 5 minutesType errors (recursive type synonym and confusing print with shows): 4 minutesThat adds up to one minute, right?
Hmmm, took 24 times longer than the title, but I did it for graphs, not trees I suppose.http://paste.lisp.org/+2R05
Took me 10 times longer :-)http://paste.lisp.org/display/128318
It likely took me a minute to cruft up a simple car/cdr/cons stack DFS version, but I succumbed to a fit of generalization and result order dinking.http://sprunge.us/PGWV?scheme
Heh, took me longer to figure out how to format the comment for blogger.com :-)def descent(node, childrenOf):..for child in childrenOf(node):....yield child....for deep in descent(child, childrenOf):......yield deep
Third try:(defun descendants^ (node)____(append (children node) (mapcan #'descendants^ (children node))))Highlighted at paste.lisp.org
Post a Comment