If you want to get a job as a software witch, you’re going to have to pass a whiteboard interview. We all do them, as engineers–often as a part of our morning ritual, along with arranging a beautiful grid of xterms across the astral plane, and compulsively running ls in every nearby directory–just in case things have shifted during the night–the incorporeal equivalent of rummaging through that drawer in the back of the kitchen where we stash odd flanges, screwdrivers, and the strangely specific plastic bits: the accessories, those long-estranged black sheep of the families of our household appliances, their original purpose now forgotten, perhaps never known, but which we are bound to care for nonetheless. I’d like to walk you through a common interview question: reversing a linked list.

First, we need a linked list. Clear your workspace of unwanted xterms, sprinkle salt into the protective form of two parentheses, and recurse. Summon a list from the void.

(defn cons [h t] #(if % h t))

“That’s not a list,” the interviewer says. “That’s an if statement.”

“What else are lists,” you reply, your eyes flashing, “But alternatives?”

user=> (def x (cons 1 (cons 2 nil)))
#'user/x
user=> (x true)
1
user=> ((x false) true)
2

“What’s x exactly?” The interviewer makes every attempt to appear friendly. Answer at the REPL, but do not be deceived for an instant. They are not a friend. Your oath at the Front Desk forbade it.

user=> x
#object[user$cons$cell__4431 0x3b89cc1c "user$cons$cell__4431@3b89cc1c"]

“To know a thing is to name it,” you advise. True names have power. The K language was invented by Ursula K. Le Guin, and is among the oldest and tersest forms of magic. To imbue a language with a letter of your own name is to give up an element of your self. Your own initials ache at the memory.

“Erm, OK, so how would you get an element out of this list?”

The expression in your mind is beautiful, unfurling like a red carpet underneath your bare feet. The Oscars were on last night, but you long for the kiss of different stars upon your naked skin, as when you dwelt in the mountains of Sørøya, and called the moon your lover. Except for the bounds check, you get it right the first time.

(defn nth [l n]
  (when l (if (= 0 n)
            (l true)
            (recur (l false) (dec n)))))

“Could you just show me, you know, a regular list? Like in Python?”

You grit your teeth, plant your feet against the floor, and dredge a pretty printer from the void. Your palms are calloused now, your eyelids limned with crystalline, soot-black snowflakes. Every action comes at cost–except, of course, for pure functions, which are side-effect free.

(defn prn-list [l]
  (print "(")
  (loop [l l]
    (if (nil? l)
      (print ")\n")
      (do (print (l true))
          (when (l false)
            (print " "))
          (recur (l false))))))

No time for descriptive variables, examples, or docstrings here. In the whiteboard interview, time is of the essence. Pretend you are a Haskell programmer, as your grandmother was, before her continuation passed.

user=> (prn-list (cons 1 (cons 2 (cons 3 nil))))
(1 2 3)

The interviewer smiles, reassured. We are on, or at least above, familiar ground. “So, to reverse it, you’d…”

You seize his hands in yours, his mind a frantic clockwork unwinding, skittering ticker-tapeworm unraveling, pitter-patter heart askance and out of place, and in the ancient tongue, recite an epigram.

(defn reverse [l]
  (loop [r nil, l l]
    (if l
      (recur (cons (l true) r) (l false))
      r)))

user=> (prn-list (reverse (cons 1 (cons 2 (cons 3 nil)))))
(3 2 1)

As you release your hold, he stutters something polite, and zips his hoodie to protect against the frost. There will be other meetings, but you need not participate. Send an eagle in your place.

They will refuse, of course, and ever so ashamed, cite a lack of culture fit. Alight upon your cloud-pine, and exit through the window. This place could never contain you.

Next: Hexing the technical interview.

Azzie
Azzie on

I’d laugh, but that had happened to me

Spelling Troll
Spelling Troll on

s/sieze/seize :)

Bill Smith
Bill Smith on

Nice writing, Aphyr. Were you reading William Gibson last night?

Cesar D
Cesar D on

this was awesome.

Blaz
Blaz on

This was seriously and awesome read. Worth a goof and a chuckle.

Eric Fode
Eric Fode on

<3

Nathan
Nathan on

Pure awesome. Thanks for writing Aphyr.

zpojqwfe1wfhiunz
zpojqwfe1wfhiunz on

@Bill, The William Gibson version would begin thusly:

It was hot, the night I burned the Seeker. Moths batted themselves to death against the humming neon signs just outside the single window in the cramped room. There were ancient electronics piled to the ceiling in here, hot new chipsets from Taiwan still unwrapped distributed unevenly amongst them. The Seeker put his hands on his hips, brushing aside the corners of his Sukajan jacket bomber jacket replica. "I heard you and Bobby were hotshots, once. Real.. artístes", he said, the last word paired with a smug grin. "Heard you could do things." "Things like what?" It's been 20 seconds and you've already wasted too many cycles with this guy. "Things like making lists, just, fold up inside themselves. Come out the other way around. Crazy things." You grit your teeth. The dex has left your system and you're starting to feel a massive drug deficiency coming on. "Crazy things cost money", you manage. The lists already unfurling in your head, you start typing as quickly as you can to hide the microtremors.
Your Fan
Your Fan on

Truly sublime.

Paul
Paul on

Excellent. Reminds me of something by China Mieville.

Aaron
Aaron on

Not Gibson. He’s obviously been reading The King Killer Chronicles by Patrick Rossfuss. “To know the name of a thing, is to have power over it”.

Nice incantations btw.

mario

DAYYYAAAAAM

Marty
Marty on

I don’t know, I sort of prefer

(defn cons [h t] #(if (or (= 0 %) %) h (if (number? %) (t (dec %)) t)))
Ahmed
Ahmed on

Someone has been reading Rothfuss :)

anonymous on

Nope, I need a false?. Better:

(defn cons [h t] #(if (or (= 0 %) (false? %)) h (if (number? %) (t (dec %)) t)))
Nijiko Yonskai
Nijiko Yonskai on

After the candidate took his leave the interviewer being bombarded with questions by the holders of steak stared out from inside the bustling warehouse wondering if he would ever truly understand what a list really is.

doktorpaine

Kyle, you beautiful, mad man.

I need to try this in my next interview. Perhaps with raw lambda calculus for shits & giggles.

anonymous on

A transliteration in Python, because why let Clojure have all the fun?:

#!/usr/bin/python def cons(if_true, if_false): return lambda which: if_true if which else if_false def reverse_but_as_list(generated_cons, the_list = []): if generated_cons(False) is not None: return reverse_but_as_list(generated_cons(False), [generated_cons(True)] + the_list) else: return [generated_cons(True)] + the_list def reverse_but_as_cons(generated_cons, the_func = None): if generated_cons(False) is not None: return reverse_but_as_cons(generated_cons(False), cons(generated_cons(True), the_func)) else: return cons(generated_cons(True), the_func) l = cons(1, cons(2, cons(3, None))) # Reverse as Python list (normal order -> output is reversed from here) print(reverse_but_as_list(l)) # Reverse as Python list (the reversed cons -> output should be the same, but in a Python list instead) print(reverse_but_as_list(reverse_but_as_cons(l)))
Riking
Riking on

In the spirit of the Python comment, I had a shot at writing this in golang. I hope you don’t mind.

I made sure to include tests, because we all know test-driven development is the wave of the present.

Forgive the generics, but this is a strictly typed language. Can’t have garbage of the wrong types polluting our beautiful lists.

package list import "io" import "fmt" // generics - swap out V1 for a new implementation type V1 int32 type I1 interface { Get() V1 Next() I1 } type T1 V1 type N1 func(bool) I1 func (t T1) Get() V1 { return V1(t) } func (t T1) Next() I1 { return nil } func (l N1) Get() V1 { return l(true).Get() } func (l N1) Next() I1 { return l(false) } var e I1 func Cons(h, t I1) N1 { return func(q bool) I1 { if q { return h } return t } } func Nth(l I1, n int) V1 { switch n { case 0: return l.Get() default: return Nth(l.Next(), n-1) } } func Print(l I1, w io.Writer) { fmt.Fprint(w, "(") for l != e { fmt.Fprint(w, l.Get()) l = l.Next() if l != e { fmt.Fprint(w, " ") } } fmt.Fprint(w, ")") } func Reverse(l I1) I1 { return reverse(e, l) } func reverse(r, l I1) I1 { if l == e { return r } return reverse(Cons(T1(l.Get()), r), l.Next()) }package list_test import "fmt" import ( "localhost.localdomain/list" "os" ) func ExampleCons() { l := list.Cons(list.T1(1), list.Cons(list.T1(2), nil)) fmt.Println(l.Get()) fmt.Println(l.Next().Get()) // Output: // 1 // 2 } func ExampleNth() { l := list.Cons(list.T1(1), list.Cons(list.T1(2), nil)) l = list.Cons(list.T1(3), l) fmt.Println(list.Nth(l, 1)) fmt.Println(list.Nth(l, 2)) // Output: // 1 // 2 } func ExamplePrint() { l := list.Cons(list.T1(1), list.Cons(list.T1(2), list.Cons(list.T1(3), nil))) list.Print(l, os.Stdout) // Output: // (1 2 3) } func ExampleReverse() { l := list.Cons(list.T1(1), list.Cons(list.T1(2), list.Cons(list.T1(3), nil))) list.Print(list.Reverse(l), os.Stdout) // Output: // (3 2 1) }
Jauzey
Jauzey on

Ah, not Rothfuss but Le Guin herself! Who else but her on the subject of Naming.

Mitch
Mitch on

And in JS, not so elegent, but can be understood by dummy like me

const cons = (a,b) => (x) => x ? a: b; const list = cons(1,cons(2,cons(3,null))); const printl = (l) => { const inner = (li,str) => { str = str + li(true); if (li(false) == null) console.log(str+')'); else { str += ', '; return inner(li(false),str) } }; return inner(l,'(') }; const reverse = (l) => { const inner = (li, data) => { const newItem = cons(li(true),data); if (li(false) == null) { return newItem; } else { return inner(li(false),newItem); } }; return inner(l,null); }; printl(list); printl(reverse(list));
anonymous on

Here’s a Perl version. I’ve tried to make it as literal as possible, translating line by line.

Some of the changes:

  • use 1 and 0 instead of true and false because Perl doesn’t have a boolean type
  • nil becomes undef, naturally
  • there’s nothing like the loop macro, so use an anonymous function instead
  • reverse is a builtin, so name the function reversed instead

This was quite fun.

use v5.16.0; use warnings; use Function::Parameters qw(:strict); fun cons($h, $t) { fun ($x) { $x ? $h : $t } } { my $x = cons 1, cons 2, undef; say $x->(1); # 1 say $x->(0)->(1); # 2 say $x; # CODE(0x947a5f8) } fun nth($l, $n) { $l and $n == 0 ? $l->(1) : __SUB__->($l->(0), $n - 1) } fun prn_list($l) { print "("; fun ($l) { !defined $l ? print ")\n" : do { print $l->(1); print " " if $l->(0); __SUB__->($l->(0)) } }->($l) } prn_list cons 1, cons 2, cons 3, undef; # (1 2 3) fun reversed($l) { fun ($r, $l) { $l ? __SUB__->(cons($l->(1), $r), $l->(0)) : $r }->(undef, $l) } prn_list reversed cons 1, cons 2, cons 3, undef; # (3 2 1)
Hisham

In Lua:

function cons(h, t) return function(x) return x and h or t end end x = cons(1, cons(2, cons(3, nil))) function nth(l, n) return n == 0 and l(true) or nth(l(false), n-1) end function prn_list(l) io.write("(") while l do io.write(l(true)..(l(false) and " " or "")) l = l(false) end io.write(")\n") end function reverse(l) local loop loop = function(r, l) return l and loop(cons(l(true), r), l(false)) or r end return loop(nil, l) end prn_list(reverse(x))

In MoonScript:

x = cons 1, cons 2, cons 3, nil prn_list = (l) -> io.write "(" while l io.write (l true) .. ((l false) and " " or "") l = l false io.write ")\n" reverse = (l) -> loop = (r, l) -> l and (loop (cons (l true), r), l false) or r loop nil, l prn_list reverse x
Hisham

Paste missed a bit of MoonScript:

cons = (h, t) -> (x) -> x and h or t nth = (l, n) -> n == 0 and (l true) or nth (l false), n-1 print nth x, 2
Shane
Shane on

As you release your hold, he stutters something polite, and zips his hoodie to protect against the frost. There will be other meetings, but you need not participate. Send an eagle in your place.

This is one of the best paragraphs ever written in English.

Marco
Marco on

And the Java version. Surprisingly it doesn’t look that bad :-)

import java.util.function.Function; public class Main { interface List<T> extends Function<Boolean, Object>{ default T head() { return (T)apply(true); } default List<T> tail() { return (List<T>)apply(false); } default T nth(int idx) { return idx == 0 ? head() : tail() == null ? null : tail().nth(idx - 1); } default String print() { return "(" + printLoop(this); } static <T> String printLoop(List<T> list) { return list.head().toString() + (list.tail() == null ? ")" : " " + printLoop(list.tail())); } default List<T> reverse() { return reverseLoop(null, this); } static <T> List<T> reverseLoop(List<T> reversed, List<T> remainder) { return remainder == null ? reversed : reverseLoop(cons(remainder.head(), reversed), remainder.tail()); } static <T> List<T> cons(T head, List<T> tail) { return (whichOne) -> whichOne ? head : tail; } } public static void main(String[] args) { List<Integer> x = List.cons(1, List.cons(2, List.cons(3, null))); System.out.println(x); System.out.println(x.head()); System.out.println(x.tail()); System.out.println(x.tail().head()); System.out.println(x.tail().tail()); System.out.println(x.nth(0)); System.out.println(x.nth(1)); System.out.println(x.nth(2)); System.out.println(x.nth(3)); System.out.println(x.print()); System.out.println(x.reverse().print()); } }
Scott Maddox
Scott Maddox on

And here it is in a language I just made up, based on De Bruijn indexed lambda calculus:

-- this is a line comment -- the lines below declare intrinsic values and functions top := intrinsic -- the singular instance of the Top type if_top := intrinsic -- returns second argument if first argument is top; -- otherwise, returns third argument concat := intrinsic -- returns the concatenation of two string literals -- the lines below define derived values and functions; backslashes create lambda abstractions true := \ \ 2 -- returns the first of two arguments false := \ \ 1 -- returns the second of two arguments pair := \ \ \ 1 2 3 -- creates a pair from two terms fst := \ 1 true -- accepts a pair and returns the first term snd := \ 1 false -- accepts a pair and returns the second term list := pair "1" (pair "2" (pair "3" top)) -- example list list_to_string := -- accepts a list and returns a string of its contents \ if_top 1 -- (with a single trailing space) (" ") (concat (concat (fst 1) (" ")) (list_to_string (snd 1))) reverse := \ if_top 1 (top) (pair (reverse (snd 1)) (fst 1)) -- the lines below are semicolon-terminated statements that are evaluated and printed list_to_string list; list_to_string (reverse list);
Aphyr on

Geo Carncross, on the k mailing list, conjured this delightful gem in k:

cons:{$[z;x;y]} nth:{$[~y;x 1;o[x 0;y-1]]} prn:{,[;")"]"("," "/${$[()~x;();x[1],o[x 0]]}x} reverse:{$[()~x;y;o[x 0;cons[x 1;y]]]}[;()]
Aphyr
Glyph

No disrespect to the previous Python poster, but I really felt like it wasn’t quite in the spirit of the post.

My own humble attempt:

cons = lambda h, t: lambda w: h if w else t x = cons(1, cons(2, None)) nth = lambda l, n: None if not l else l(True) if n == 0 else nth(l(False), n-1) prn_list = lambda l: "[" + ", ".join(map(str, iter(lambda n=[0]: nth(l, n.append(n[0]+1) or n.pop(0)), None))) + "]" reverse = lambda l, r=None: r if l is None else reverse(l(False), cons(l(True), r))

(available as a Jupyter notebook here https://gist.github.com/glyph/0a77a80e4f2d1cf24514f8cd38617c8b)

Glyph

Okay, I’m sorry, relying upon the iterator protocol is equally gauche. Please accept this alternate implementation of prn_list, which more properly relies only upon optional parameters and string concatenation for a recursive definition:

prn_list = lambda l, b="[", m="", e="]": ( b + ("" if l is None else m + str(l(True)) + prn_list(l(False), "", ", ", "")) + e )
Wodin
Wodin on

For the person who asked whether this was lisp:

Yes, it’s a lisp called Clojure.

Cory
Cory on

We compulsively run ls in every directory for the same reason we prefer to walk around our homes with the light on. The further you go without reorienting yourself, the more likely you make a mistake.

botchagalupe

Young man, you are undeniably brilliant. I would go further than Gibson. I would say you are the David Foster Wallace of distributed computing. With that said, things use to be a lot easier back in my day…

Here’s my tongue and cheek attempt to tell how it was back in the 1980’s with a couple of caveats…

  • I haven’t coded IBM 370 Assembler since 1988.
  • I don’t have a mainframe to test the code.
  • If there are actual coding errors it’s just a joke anyway.
  • Please reread #3.

You might have also noticed that I cheated in a few places.. just a little bit. However, unless I missed the main point… WTF is a list anyway….

.... .... some entry stuff .... LA R1,ALIST PUT 0(,R1),OUTREC MVI 1(R1),=X'F3' MVI 5(R1),=X'F1' PUT 0(,R1),OUTREC * * At this point you're kind of done.. however, if they insist. * LA R1,ALIST SR R2,R2 LOOP1 LA R2,1(,R2) MVC R2(1,R1),0(R2) LA R2,1(,R2) TR R2(1,R1),HEXTAB1 BNZ LOOP1 PUT ALIST,OUTREC LA R1,ALIST SR R2,R2 LOOP2 LA R2,1(,R2) MVC R2(1,R1),0(R2) LA R2,1(,R2) TR R2(1,R1),HEXTAB2 BNZ LOOP2 PUT ALIST,OUTREC .... .... some other clean up stuff .... ALIST DC X'4DF16BF26BF35D' OUTREC DS CL6 HEXTAB1 DS XL256'00' DC C'123' HEXTAB2 DS XL256'00' DC C'321'
David Mathers
David Mathers on

Ruby:

def cons(h, t) -> w { w ? h : t } end x = cons(1, cons(2, nil)) x.(true) x.(false).(true) def nth(l, n) return if l.nil? if n.zero? l.(true) else nth(l.(false), n.pred) end end def prn_list(l) print '(' until l.nil? print l.(true) print ' ' unless l.(false).nil? l = l.(false) end puts ')' end prn_list(cons(1, cons(2, cons(3, nil)))) def reverse(l) r = nil until l.nil? r = cons(l.(true), r) l = l.(false) end r end prn_list(reverse(cons(1, cons(2, cons(3, nil)))))
Wodin
Wodin on

@botchagalupe

Here’s a mainframe for you: http://www.hercules-390.org/

anonymous on

“People create programs to direct processes. In effect, we conjure the spirits of the computer with our spells.” - SICP

anonymous on

reverse(list); EOF

anonymous on

Smalltalk:

| cons x nth printList reverse | cons := [ :h :t | [:w | w ifTrue: [ h ] ifFalse: [ t ] ] ]. x := cons value: 1 value: (cons value: 2 value: nil). Transcript show: (x value: true); cr. Transcript show: ((x value: false) value: true); cr. nth := [ :l :n | (n == 1) ifTrue: [ l value: true ] ifFalse: [nth value: (l value: false) value: (n-1)]]. x := cons value: 1 value: (cons value: 2 value: (cons value: 3 value: nil)). Transcript show: (nth value: x value: 1 ); cr. Transcript show: (nth value: x value: 2 ); cr. Transcript show: (nth value: x value: 3 ); cr. printList := [ :l | | p | p := [ :l1 | l1 ifNotNil: [ Transcript show: (l1 value: true). (l1 value: false) ifNotNil: [ Transcript show: ' ' ]. p value: (l1 value: false). ] ]. Transcript show: '('. p value: l. Transcript show: ')'; cr. ]. printList value: (cons value: 1 value: (cons value: 2 value: (cons value: 3 value: nil))). reverse := [ :l | | r l1 | r := nil. l1 := l. [l1 notNil] whileTrue: [ r := cons value: (l1 value: true) value: r. l1 := l1 value: false. ]. r ]. printList value: (reverse value: (cons value: 1 value: (cons value: 2 value: (cons value: 3 value: nil)))).
Drahflow

Sorry, could not resist to do it Elymas:

{ ==h { h ? 1 }_ } =*cons { } "3" cons "2" cons "1" cons ==x x dump { =*l _ { 1 sub 1 l -- nth } { -- 0 l -- } ? * } =*nth { [ -01 { 0 -01*1 -01 } { 1 -01* -- } loop -1 ] dump } =*dumpList x dumpList { { { } } -01 { =*r =*l 0 l { { -1*0 cons } 1 l -- |r r } rep } _ * * } =*reverse x reverse dumpList
inuxela
inuxela on

Maxscript:

`fn cons x y = ( local s=struct s ( x, y, fn l q=if q then x else y ) (s x y).l )

fn nth n x = ( if n == 0 then x true else nth (n-1) (x false) )

fn prnList x = ( format “#(” while x != undefined do ( format “%” (x true) x = x false if x != undefined then format “, ” ) format “)\n” )

fn rev x = ( local r = undefined while x != undefined do ( r = cons (x true) r x = x false ) r )

x = (cons 1 (cons 2 (cons 3 undefined))) prnList (rev x)`

Arlo
Arlo on

To check relative speed, I ran Glyph’s python version x = cons(1, cons(2, cons(3, cons(4, None)))) s = prn_list(reverse(x)) against boring python a = [1,2,3,4] a.reverse() b=str(a) for 10,000 iterations.

One one hand, the standard python version was a lot faster, taking 0.0979869365692s against the witchy code’s 0.65337896347s.

On the other hand, the witchy code was slower by a factor of 6.66.

Make of that what you will.

Zyrill
Zyrill on

You should write a novel, @zpojqwfe1wfhiunz. I’d buy it. :)

Sub-Lunar
Sub-Lunar on

The JavaScript and one of the Python versions above seem to be missing the nth function. Here’s a slightly terser JS version, including nth:

const cons = (h, t) => b => b ? h : t const nth = (l, n) => n === 0 ? l(true) : nth(l(false), n - 1) const prnList = (l, s='(') => l ? prnList( l(false), s + l(true) + (l(false) ? ' ' : '')) : console.log(s + ')') const reverse = (l, r=null) => l ? reverse(l(false), cons(l(true), r)) : r const list = cons(1, cons(2, cons(3, null))) prnList(list) console.log(nth(list, 1)) prnList(reverse(list))
Sub-Lunar
Sub-Lunar on

Forgive my rudeness; I forgot to mention that

  1. it was of course not my intention to disrespect or condescend to any other JavaScript implementations suggested prior to mine (not that I was accused of doing so, but anyway), and
  2. I enjoyed reading the original post a lot. I am looking forward to more excellent writing on this blog.
NumberCruncher
NumberCruncher on

Loved it …

Didn’t do something this good for a technical interview at an unnamed hedge fund in NYC, but I didn’t do the python version of what they wanted, as it was so trivial to do in Perl. The interviewer was visibly upset that I did that.

Add to the fact that I didn’t have some random arcana committed to memory about specific bash syntax/example, so I made the terrible error of using a (wait for it) … man page … to look up the specific syntax and examples of what I wanted to do. Since they didn’t install man pages, I ssh'ed to one of my machines, whilst this person sat dumbfounded, complaining later that they wanted to see my google-foo.

Yeah.

Send an eagle.

Ladd

Here’s a rendition of the first part in C.

#include <stdio.h> #include <stdlib.h> #define NEW(type, name, ...) type *name; name = malloc(sizeof(*name)); \ *name = (type) { __VA_ARGS__ }; #define FALSE (void *) 0 #define TRUE (void *) 1 typedef void *(*_func)(void *d, void *x); typedef struct { _func f; void *d; } closure; typedef struct { void *h; void *t; } list_elem; // Almost a lambda function void *_cons(void *_d, void *x) { list_elem *d = _d; void *r = x ? d->h : d->t; return r; } closure *cons(void *h, void *t) { NEW(list_elem, d, h, t); NEW(closure, c, _cons, d); return c; } closure *num(long n) { NEW(long, np, n); NEW(closure, c, NULL, np); return c; } closure *call(closure *c, void *x) { return (c && c->f) ? c->f(c->d, x) : c; } long get_num(closure *c) { return *(long *) c->d; } void prn_list(closure *c) { printf("("); } int main() { closure *c, *r; c = cons(num(1L), cons(num(2L), NULL)); r = call(c, (void *) 1); printf("%ld\n", get_num(r)); r = call(call(c, FALSE), TRUE); printf("%ld\n", get_num(r)); return 0; }
Kekeli
Kekeli on

Happened to read this a day after Ursula K Leguin’s passing. The article is a treat in itself, and the K language aside a nice reminder of her true power with names.

Carl Mäsak

I would just like to note my absolute admiration of the writing in this post, and the subsequent two.

Others have said it too, but I would happily pay for stories like this.

Steven Dunham
Steven Dunham on

I’m a bit late to the game here, but it doesn’t look like anyone gave the church-encoded version. With an appropriate definition of true and false, we don’t need if:

(defn t [x y] x) (defn f [x y] y) (defn cons [h t] #(% h t)) (defn nth [l n] (when l (if (= 0 n) (l t) (recur (l f) (dec n))))) (defn prn-list [l] (print "(") (loop [l l] (if (nil? l) (print ")\n") (do (print (l t)) (when (l f) (print " ")) (recur (l f)))))) (defn reverse [l] (loop [r nil, l l] (if l (recur (cons (l t) r) (l f)) r))) (prn-list (reverse (cons 1 (cons 2 (cons 3 nil)))))
Bd

Any wizard here that can reverse this? https://en.scratch-wiki.info/wiki/Linked_List

Mark
Mark on

Nice! Wonderful story.

Typo: eyelids - lined - with crystalline

Laramie
Laramie on

You can do this in c++, it’s easier with concepts.

#include #include

template struct cons_impl { auto operator()(std::true_type) { return h; } auto operator()(std::false_type) { return t; } H h; T t; };

template constexpr auto cons(H && h, T&& t) { return cons_impl{ h, t }; }

std::any nth(nullptr_t, int n) { return {}; }

template std::any nth(L&& l, int n) { return (n == 0) ? std::any{l(std::true_type{})} : nth(l(std::false_type{}), n-1); }

void print_space_impl(nullptr_t) {}

template void print_space_impl(L&& l) { std::cout << “ ”; }

void print_list_impl(nullptr_t) { std::cout << “)\n”; }

template void print_list_impl(L&& l) { std::cout << l(std::true_type{}); auto r = l(std::false_type{}); print_space_impl®; print_list_impl®; }

template void print_list(L&& l) { std::cout << “(”; print_list_impl(std::forward(l)); }

template auto reverse_1_(L&& l, auto x);

auto reverse_2_(nullptr_t, auto x) { return x; }

template auto reverse_2_(L&& l, auto x) { return reverse_1_(l, x); }

template auto reverse_1_(L&& l, auto x) { auto y = cons(l(std::true_type{}), x); return reverse_2_(l(std::false_type{}), y); }

template auto reverse(L&& l) { return reverse_1_(l, nullptr); }

int main(int argc, char** argv) {

auto c = cons(1, cons(2, nullptr)); std::cout << c(std::true_type{}) << std::endl; std::cout << c(std::false_type{})(std::true_type{}) << std::endl; std::cout << std::any_cast<int>(nth(c, 1)) << std::endl; print_list(c); std::cout << std::endl; print_list(reverse(c)); std::cout << std::endl;

}

lechimp-p

I really love this post. I think the implementation in PHP is missing, though:

<?php function cons($a, $b) { return function ($x) use ($a, $b) { return $x ? $a : $b; }; } function nth($n, $l) { if ($n == 0) { return $l(true); } if (is_null($l)) { return null; } return nth($n-1, $l(false)); } function pprint($l) { echo "["; while($l) { echo $l(true); $l = $l(false); if (!is_null($l)) { echo ", "; } } echo "]"; } function reverse($l, $r = null) { if (is_null($l)) { return $r; } return reverse($l(false), cons($l(true), $r)); } pprint(reverse(cons(1, cons(2, cons(3, null)))));
K Cartlidge
K Cartlidge on

Love the tale, and the Gibson version is great too.

As an aside for Mark (2020/10/09, “eyelids lined with crystalline”) - the usage of “limned” here is correct, appropriate, and fitting.

shiki
shiki on

The Earthsea reference had me dying lmao

Arne Babenhauserheide

I used the Hacking Key and entered code {white-space: pre-wrap} to enjoy the examples a lot more :-)

Loved the story and the comments! Thank you!

JRF

Userstyle (for e.g. Stylus) to better enjoy the code posted in the comments:

@-moz-document domain("aphyr.com") {
code.block {
	white-space: pre-wrap;
	display: block;
}
}
Sistem Informasi

so how would you get an element out of this list?

Post a Comment

Comments are moderated. Links have nofollow. Seriously, spammers, give it a rest.

Please avoid writing anything here unless you're a computer. This is also a trap:

Supports Github-flavored Markdown, including [links](http://foo.com/), *emphasis*, _underline_, `code`, and > blockquotes. Use ```clj on its own line to start an (e.g.) Clojure code block, and ``` to end the block.