Topic: [Challenge (?)] F# List module functions -> AutoLISP

[gile]

Hi,

To follow this thread and this reply, I purpose to collect in this thread some F# List module functions brought to AutoLISP.
F# and LISP are very different but both support functional programming and F# lists are the same structure LISP lists (cons cells tree).

These functions are described here.

Some already exist in AutoLISP:
List.append or List.concat -> append
List.exists -> vl-some
List.filter -> vl-remove-if-not
List.forall -> vl-every
List.iter -> foreach
List.map, list.map2, List.map3 -> mapcar
...

Some others have no AutoLISP built-in equivalent function, I thaught it could be a challenge to try to define them in AutoLISP.

To understand these F# functions, the function 'signature' can be helpfull.
The signature shows the arguments and the return value types. If the the function requires another function as argument (higher order function), this argument appears as its signature between parents.
Example with List.map (equivalent to mapcar with a single list):

List.map : ('T -> 'U) -> 'T list -> 'U list

This means the function requires as arguments: a function and a list which elements are the same type (T) and returns a list of type U elements (T and U can be the same or different types).
The argument function requires a type T value and returns a type U value.

[gile]

Here're some.

List.fold and List.foldBack

Code: [Select]

;; gc:fold
;; Applies a function to each element of the list threading an accumulator argument through the computation.
;; Take the second argument, and apply the function to it and the first element of the list.
;; Then feed this result into the function along with the second element and so on.
;; Return the final result.
;; If the input function is f and the elements are i0...iN then computes (f (... (f s i0) i1 ...) iN).
;;
;; Signature: ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State
(defun gc:fold (fun acc lst)
  (setq fun (eval fun))
  (foreach n lst (setq acc (fun acc n)))
)

;; gc:foldBack
;; Applies a function to each element of the list threading an accumulator argument through the computation.
;; If the input function is f and the elements are i0...iN then computes (f i0 (...(f iN s))).
;;
;; Signature: ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State
(defun gc:foldBack (fun acc lst)
  (setq fun (eval fun))
  (foreach n (reverse lst) (setq acc (fun acc n)))
)
Examples:

_$ (gc:fold '(lambda (a e) (strcat a ", " (itoa e))) "0" '(1 2 3))
"0, 1, 2, 3"

_$ (gc:foldBack '(lambda (a e) (strcat a ", " (itoa e))) "0" '(1 2 3))
"0, 3, 2, 1"

List.scan and List.scanBack

Code: [Select]

;; gc:scan
;; Applies a function to each element of the list threading an accumulator argument through the computation.
;; Take the second argument, and apply the function to it and the first element of the list.
;; Then feed this result into the function along with the second element and so on.
;; Returns the list of intermediate results and the final result.
;;
;; Signature: ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State list
(defun gc:scan (fun acc lst)
  (setq fun (eval fun))
  (cons acc (mapcar (function (lambda (x) (setq acc (fun acc x)))) lst))
)

;; gc:scanBak
;; Like foldBack, but returns both the intermediary and final results
;;
;; Signature: ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State list
(defun gc:scanBack (fun acc lst / res)
  (reverse (gc:scan fun acc (reverse lst)))
)
Examples:

_$ (gc:scan '(lambda (a e) (strcat a "," (itoa e))) "0" '(1 2 3))
("0" "0,1" "0,1,2" "0,1,2,3")

_$ (gc:scanBack '(lambda (a e) (strcat a "," (itoa e))) "0" '(1 2 3))
("0,3,2,1" "0,3,2" "0,3" "0")

List.reduce and List.reduceBack

Code: [Select]

;; gc:reduce
;; Apply a function to each element of the list threading an accumulator argument through the computation.
;; Apply the function to the first two elements of the list.
;; Then feed this result into the function along with the third element and so on. Return the final result.
;; If the input function is f and the elements are i0...iN then computes (f (... (f i0 i1) i2 ...) iN).
;;
;; Signature: ('T -> 'T -> 'T) -> 'T list -> 'T
(defun gc:reduce (fun lst / res)
  (setq fun (eval fun)
res (car lst)
  )
  (foreach n (cdr lst)
    (setq res (fun res n))
  )
)

;; gc:reducBack
;; Applies a function to each element of the list threading an accumulator argument through the computation.
;; If the input function is f and the elements are i0...iN then computes (f i0 (...(f iN-1 iN))).
;;
;; Signature: ('T -> 'T -> 'T) -> 'T list -> 'T
(defun gc:reduceBack (fun lst / res)
  (setq fun (eval fun)
lst (reverse lst)
res (car lst)
  )
  (foreach n (cdr lst)
    (setq res (fun n res))
  )
)
Examples:

_$ (gc:reduce '(lambda (x y) (+ (* 2 x) y)) '(1 2 3 4))
26
_$ (+ (* 2 (+ (* 2 (+ (* 2 1) 2)) 3)) 4)
26

_$ (gc:reduceBack '(lambda (x y) (+ (* 2 x) y)) '(1 2 3 4))
16
_$ (+ (* 2 1) (+ (* 2 2) (+ (* 2 3) 4)))

List.permute

Code: [Select]

;; gc:permute
;; Returns a list with all elements permuted according to the specified permutation.
;;
;; Signature: (int -> int) -> 'T list -> 'T list
(defun gc:permute (fun lst / i)
  (setq fun (eval fun)
i   -1
  )
  (mapcar 'car
  (vl-sort
    (mapcar '(lambda (x) (cons x (fun (setq i (1+ i))))) lst)
    (function (lambda (x1 x2) (< (cdr x1) (cdr x2))))
  )
  )
)
Examples:

_$ (gc:permute '(lambda (x) (rem (+ x 3) 6)) '("a" "b" "c" "d" "e" "f"))
("d" "e" "f" "a" "b" "c")

_$ (gc:permute '(lambda (x) (if (= 0 (rem x 2)) (1+ x) (1- x))) '("a" "b" "c" "d" "e" "f" "g"))
("b" "a" "d" "c" "f" "e" "g")

[gile]

This one is not from the F# List module but from the Seq one.
F# sequences are logical series of elements all of one type. They can be converted into lists.
F# sequences are 'lazy', and can be infinite, the elements are computed only as required.
As LISP list can't be infinite, the argument function which generates each sequence element needs to have break loop condition which returns nil.

Seq.unfold

Code: [Select]

;; gc:unfold
;; Returns a list that contains the elements generated by the given computation.
;; The given initial state argument is passed to the element generator.
;; For each list elements in the stream are generated on-demand by applying the element generator,
;; until a nil value is returned by the element generator.
;; Each call to the element generator returns a new residual state.
;; The generator have to return a dotted pair (or a list) or nil to break the loop.
;; The pair 'car' is a new result to add to the list and 'cdr' the new state.
;;
;; Signature: ('State -> ('T . 'State)) -> 'State -> 'T list
(defun gc:unfold (fun state / res lst)
  (setq fun (eval fun))
  (reverse
    (while (setq res (fun state))
      (setq state (cdr res)
    lst   (cons (car res) lst)
      )
    )
  )
)
Examples:

Binary codes lower than 300

_$ (gc:unfold '(lambda (x) (if (< x 300) (cons x (* 2 x)))) 1)
(1 2 4 8 16 32 64 128 256)

The break condition of the generator function is: state < 300.
The state is succesively passed as argument to the generator which returns a dotted pair: (result . modified_state)
1 -> (1 . 2)
2 -> (2 . 4)
4 -> (4 . 8)
8 -> (8 . 16)
...
256 -> (256 . 512)
512 -> nil

Fibonacci sequence

Code: [Select]

(defun fib (p)
  (if (< (cdr p) 1000)
    (cons (cdr p) (cons (cdr p) (+ (car p) (cdr p))))
  )
)
(gc:unfold 'fib '(1 . 1))Returns (1 2 3 5 8 13 21 34 55 89 144 233 377 610 987)
In this case, as the initial state is a dotted pair, each element returned by the generator will be a 'dotted list':
(fib '(1 . 1) -> (1 1 . 2)
(fib '(1 . 2) -> (2 2 . 3)
(fib '(2 . 3) -> (3 3 . 5)
(fib '(3 . 5) -> (5 5 . 8)
...
(fib '(610 . 987)) -> (987 987 . 1597)
(fib '(987 . 1597)) -> nil

A different way for a Fibonacci sequence in a defun function using a counter value as break condition:

Code: [Select]

(defun fibonacci (len)
  (gc:unfold
    '(lambda (x)
       (if (< (caddr x) len)
(list (cadr x) (cadr x) (+ (car x) (cadr x)) (1+ (caddr x)))
       )
     )
    '(1 1 0)
  )
)(fibonacci 5) returns (1 2 3 5 8)
Here, the state is a list which first item is the result to add to the return list, the second is to be used with the first to generate the next result and state, the third is the counter.
The lambda function (generator) returns succesively:
'(1 1 0) -> (1 1 2 1)
'(1 2 1) -> (2 2 3 2)
'(2 3 2) -> (3 3 5 3)
'(3 5 3) -> (5 5 8 4)
'(5 8 4) -> (8 8 13 5)
'(8 13 5) -> nil

[chlh_jd]

Highbrow Gile 
It's new way to improve the efficiency of LISP !
Maybe, List some of the fast algorithm for cons cell  easier for All to accept these .