remove¶

   [1 2 3 4] 5 remove
------------------------
      [1 2 3 4]

   [1 2 3 4] 2 remove
------------------------
      [1 3 4]

   [] a remove
------------------------
      []

First attempt¶

First let's handle the case of an empty list:

remove == [pop not] [pop] [remove'] ifte

For non-empty lists, the predicate and base case are easy:

remove' == [swap first =] [pop rest] [R0] [R1] genrec

The recursive branch:

[1 2 3 4] 3 R0 [remove'] R1

For R0 use [uncons] dip:

[1 2 3 4] 3 [uncons] dip [remove'] R1
[1 2 3 4] uncons 3 [remove'] R1
1 [2 3 4] 3 [remove'] R1

For R1 let's try i cons:

1 [2 3 4] 3 [remove'] i cons
1 [2 3 4] 3 remove' cons
...
1 2 [3 4] 3 remove' cons cons
...
1 2 [4] cons cons
...
[1 2 4]

Ergo:

remove' == [swap first =] [pop rest] [[uncons] dip] [i cons] genrec
remove  == [pop not] [pop] [remove'] ifte

So far so good but I made a mistake. The recursive part doesn't handle empty lists, so it's broken for the case of the item not being in the list:

Second attempt¶

remove == [pop not] [pop] [R0] [R1] genrec
remove == [pop not] [pop] [R0 [remove] R1] ifte

Non-empty:

[a b c] item R0 [remove] R1


                   R0 [remove] R1
-----------------------------------------------------
   [swap first =] [pop rest] [E1 [remove] E2] ifte

Recursive branch:

[a b c] d E1 [remove] E2

With:

E1 == [uncons] dip
E2 == i cons

[a b c] d [uncons] dip [remove] i cons
a [b c] d [remove] i cons
a [b c] d remove cons

How to make it?

R0 == [swap first =] [pop rest]

Then we want:

R1 == [[uncons] dip [remove] i cons] ifte

But of course [remove] can't appear in there like that, we have to package it up:

R1 == [i cons] cons [[uncons] dip] swoncat ifte

Or better yet:

[[uncons] dip remove cons] ifte

R1 == [cons] concat [[uncons] dip] swoncat ifte

Clunky, but it works:

remove == [pop not] [pop] [[swap first =] [pop rest]] [[cons] concat [[uncons] dip] swoncat ifte] genrec

Third attempt¶

What if we let [remove] be on the stack instead of building the else-part each iteration?:

remove == [pop not] [pop] []        [[P] [THEN] [ELSE] ifte] genrec
remove == [pop not] [pop] [ [remove] [P] [THEN] [ELSE] ifte] ifte

So:

[a b c] item [remove] [P] [THEN] [ELSE] ifte

P == pop swap first =

THEN == popop rest

ELSE == ...

Hmm...

[a b c] item [remove] ELSE
[a b c] item [remove] [uncons] dipd i cons
a [b c] item [remove] i cons
a [b c] item remove cons
...
a [b c] cons
[a b c]

So:

ELSE == [uncons] dipd i cons

And:

remove == [pop not] [pop] [] [[pop swap first =] [popop rest] [[uncons] dipd i cons] ifte] genrec