Summary


Functions for folding and unfolding a cons of two lists.
   '(() . ())  ==  '(() . nil)  ==  '(())  ==  '(nil)


Any list becomes a foldy by consing nil with it.

   (setq any-list '(one two))

   (cons nil any-list)
     ->  '(() . (one two))
     ==  '(() . (one two . nil))
     ==  '(() one two . ())
     ==  '(() one two)


Folding puts list items from the cdr into the car
 one at a time, thereby in reverse order.

Whereas the cadr was initially the first list item
 (after the empty list), folding results in the next
 cadr thereafter becoming the "current item".

The caar (prior) and cadr (current) expose the middle items
 as the crease in the foldable list.

When there are no more items to fold into the car,
 then the cdr is nil and potentially represents
 either "no current item" or "empty selection",
 if desired.


Moving all the items from the cdr into the list in the car
 essentially flips over (reverses) the whole list.

   '(nil one two)  ==  '(() one two)       ; same

                   ->  '((one) two)        ; creased

                   ->  '((two one))        ; flipped
                   ==  '((two one) . nil)  ; same
                   ==  '((two one) . ())   ; same


Unfolding is the reversal of folding,
 moving items from the list in the car into the cdr.

   '((two one))  ->  '((one) two)   ; creased
                 ->  '(() one two)  ; flopped


In other words, a foldy is a normal list of a list.
 Nothing special about one, this is just an approach.
 It is breaking a list in half and exposing its middle,
 thereby retaining the current position, too.
All done within itself, emerging naturally with no need
 for additional variables.
|#


#|
This emerges in the universe on its own, as all has.
|#


#|
Content outline


* Requirements

* Premise, an intro to #'cons and nil

* Basic approaches to folding and unfolding

* General function use and naming conventions


* Ancillary functions for a foldable list, a.k.a. foldy.
  Independent from each other.

 * Example of using these functions

 * defun fold-one.nu
    Move first item of second half to first half.

 * defun fold-until.nu
    Move some items from second half to first half.

 * defun fold-all.nu
    Move all items from second half to first half.

 * defun unfold-one.nu
    Move first item of first half to second half.

 * defun unfold-until.nu
    Move some items from first half to second half.

 * defun unfold-all.nu
    Move all items from first half to second half.

|#


#|#
Requirements


This was experienced within:
 Steel Bank Common Lisp (SBCL) 2.1.0
 sbcl.org
|#


#|#
Premise, an intro to #'cons and nil.


Embracing items with parentheses
 acknowledges those items
 are associated with each other.

Nil is an empty list,
 as in "nothing in list".
 But that also asserts "Nil Is a List"
 rather than nothingness itself.
 It has become the mnemonic name
 for an empty set of parentheses.
   nil  ==  ()
        ==  '() ; quoted form

A list of one item
 is never notated as a list,
 t.i. it has no parentheses.
 It is written simply as the item itself,
 for there are no other items associated.

A list of more than one item
 is notated as a dotted list,
 with a spaced separated period
 before its final item.
   '(one two . three)

A list with nil as its final item
 is commonly abbreviated
 without dotting with nil.
   '(one . nil)  ==  '(one)

A list of items without
 a dotted final item
 has visually consistent
 delimitation, thereby
 is a "proper list".
But as a list without
 a dotted final item,
 a proper list is merely
 the abbreviated form
 for its items dotted with nil
 as the final item.
   '(one)  ==  '(one . nil)

As such, a proper list with only nil
 is a list with an empty list:
   '(nil)  ==  '(())
 but is also the abbreviated form
 for a list of items dotted with nil
 as its final item:
   '(nil)  ==  '(nil . nil)
 which is a dotted list of two lists:
   '(nil)  ==  '(() . ())


Consing constructs a dotted list.
   (cons 'one 'two)
     ->  '(one . two)

Multiple consing results in
 the last item added
 becoming the first.
   (cons 'three       ; second cons
    (cons 'one 'two)) ; first cons
      ->  '(three one . two)

Consing an item with nil
 results in a proper list,
 because a proper list
 is the abbreviated form
 for its items dotted with nil
 as its final item.
   (cons 'three            ; third cons
    (cons 'two             ; second cons
     (cons 'one nil)))     ; first cons
       ->  '(three two one . nil)
       ==  '(three two one . ())
       ==  '(three two one)


A proper list beginning with nil
 begins and ends with a list.
   (cons nil '(one))
     ->  '(nil one)
     ==  '(nil one . nil)
     ==  '(()  one .  ())
|#


#|#
Basic approaches to folding and unfolding.


There is nothing special about a foldy,
 because it is simply a list of a list.

Basic shifting can be done by copying
 from one list into the other before removing,
 or remove then insert in the other list.

When the list of items are all in the cdr,
 then it is considered completely unfolded.
 Therefore, the first item of the list
 is the car of the cdr.
As such, the car of the cdr is generally considered
 the current item of the list.

When the list of items are all in the car,
 then it is considered completely folded.
 Therefore, the current item is nil,
 t.i. there is no current item.
That can represent an empty selection.


For example, fold an item from the second half
 to the first.

   ; Add to first half an item from second half.
   (setf (car foldy)
    (cons
     (cadr foldy)
     (car foldy)))

   ; Drop the first item of second half.
   (setf (cdr foldy)
    (cddr foldy))


Unfolding an item from the first half
 is simply the reverse.

   ; Add to second half an item from first half.
   (setf (cdr foldy)
    (cons
     (caar foldy)
     (cdr foldy)))

   ; Drop the first item of first half.
   (setf (car foldy)
    (cdar foldy))


Or, consider using the #'push and #'pop macros.

   ; Fold:
   ;  Move an item from second half to first half.
   (push
    (pop (cdr foldy))
    (car foldy)

   ; Unfold:
   ;  Move an item from first half to second half.
   (push
    (pop (car foldy))
    (cdr foldy)
|#


#|
Hereafter, there be code.
|#

#|#
General function use and naming conventions.


".nu": Arbitrary suffix for preventing name collisions,
       as in "named uniquely" or "now unique".


Trace the source of variables by prefixing a letter
 representing that source.

   defun args prefix:  F for "function"
     let args prefix:  L for "let"
  lambda args prefix:  A for "anonymous function"

Combine A and L prefixes by depth, thereby revealing scope
 and discouraging perplexation.  For example:

                       defun args  ->  F prefix
                 defun > let args  ->  L prefix
  defun > let > let > lambda args  ->  LLA prefix
|#


#|#
Functions.


Independent from each other.  Each modifies the foldy
 and then returns the foldy.


For example, consider wrapping around from
 the first item to the last item.  Recall,
 the car of the cdr is generally considered
 the current item of a foldable list.

First, fold everything into the list in the car,
 which essentially reverses the whole list.
 Its first item is the last item of the list.
Then unfolding one item would move the car
 of the reversed list into the cdr, making
 the last item of the list as the current item
 of the list.

   (setq foldy '(() one two three))

   (fold-all.nu foldy)
     -> '((three two one))

   (unfold-one.nu foldy)
     -> '((two one) three)

Or, combine them:

   (unfold-one.nu
    (fold-all.nu foldy))
|#


;#
(defun
fold-one.nu
(Ffoldy)
"Move first item of second half to first half.

Moves an item only when cdr is non-nil.

Modifies original, but also returns foldy
 as a convenience."
 ;;Ensure there is an item in second half to move.
(and(cdr Ffoldy)
 ;;;Move first item of second half to first half.
(push(pop(cdr Ffoldy))(car Ffoldy)))
 ;;Return foldy as convenience for further use.
Ffoldy)


;#
(defun
fold-until.nu
(Ffoldy Fstop)
"Move some items from second half to first half.

Moves an item only when cdr is non-nil.

Fstop is either a lambda or a quoted function
 for #'funcall.  It receives a single item
 (the cadr of Ffoldy) and returns a non-nil value
 for stopping at that item, leaving it as the cadr.

Each moved item becomes the new caar of Ffoldy.

Modifies original, but also returns foldy
 as a convenience."
(do
();no variables
 ;;;Common Lisp #'do is actually "do until non-nil".
((or
 ;;;;;Stop when no more items, t.i. cdr is nil.
(not(cdr Ffoldy))
 ;;;;;Or stop when Fstop returns non-nil,
(funcall Fstop(cadr Ffoldy))))
 ;;;Move first item of second half to first half.
(push(pop(cdr Ffoldy))(car Ffoldy)))
 ;;Return foldy as convenience for further use.
Ffoldy)


;#
(defun
fold-all.nu
(Ffoldy)
"Move all items from second half to first half.

Moves an item only when cdr is non-nil.

Modifies original, but also returns foldy
 as a convenience."
(do
();no variables
 ;;;Common Lisp #'do is actually "do until non-nil".
 ;;; Stop when no more items to move, t.i. cdr is nil.
((not(cdr Ffoldy)))
 ;;;Move first item of second half to first half.
(push(pop(cdr Ffoldy))(car Ffoldy)))
 ;;Return foldy as convenience for further use.
Ffoldy)


;#
(defun
unfold-one.nu
(Ffoldy)
"Move first item of first half to second half.

Moves an item only when car is non-nil.

Modifies original, but also returns foldy
 as a convenience."
 ;;Ensure there is an item in first half to move.
(and(car Ffoldy)
 ;;;Move first item of first half to second half.
(push(pop(car Ffoldy))(cdr Ffoldy)))
 ;;Return foldy as convenience for further use.
Ffoldy)


;#
(defun
unfold-until.nu
(Ffoldy Fstop)
"Move some items from first half to second half.

Moves an item only when car is non-nil.

Fstop is either a lambda or a quoted function
 for #'funcall.  It receives a single item
 (the caar of Ffoldy) and returns a non-nil value
 for stopping at that item, making it the cadr.

Each moved item becomes the new cadr of Ffoldy.

Modifies original, but also returns foldy
 as a convenience."
(do
();no variables
(;;;;Common Lisp #'do is actually "do until non-nil".
(or
 ;;;;;Stop when no more items, t.i. car is nil.
(not(car Ffoldy))
 ;;;;;Or stop when Fstop returns non-nil,
(funcall Fstop(caar Ffoldy)))
 ;;;;Move one more item after completion so as
 ;;;; to coordinate with #'fold-until.nu results.
(and(car Ffoldy)
(push(pop(car Ffoldy))(cdr Ffoldy))))
 ;;;Move first item of first half to second half.
(push(pop(car Ffoldy))(cdr Ffoldy)))
 ;;Return foldy as convenience for further use.
Ffoldy)


;#
(defun
unfold-all.nu
(Ffoldy)
"Move all items from first half to second half.

Moves an item only when car is non-nil.

Modifies original, but also returns foldy
 as a convenience."
(do
();no variables
 ;;;Common Lisp #'do is actually "do until non-nil".
 ;;; Stop when no more items to move, t.i. car is nil.
((not(car Ffoldy)))
 ;;;Move first item of first half to second half.
(push(pop(car Ffoldy))(cdr Ffoldy)))
 ;;Return foldy as convenience for further use.
Ffoldy)