GoferLists - Advanced List Processing Functions
GoferLists is a library of advanced list operations mostly borrowed from the Haskell programming language. The library was originally written by Jarno Peschier and ported to SysRPL by Luis Morales Boisset. The current 1.0 version was put together by Albert Graef. It fixes a couple of minor bugs in the SysRPL version and adds a bunch of new functions to the library. GoferLists is written 100% in SysRPL and hence the functions are reasonably efficient.
The main advantage of GoferLists is that it supplies a fairly standard set of tried and proven list processing functions found in most modern functional programming languages, and that corner cases like empty input lists are treated in a consistent fashion. This makes these functions much easier to use than the builtin list operations such as DOLIST and STREAM.
Download and Installation
You can download the current version of GoferLists here: GoferLists-1.0.zip
Make sure you back up your calc before trying GoferLists, as this is still beta software. Transfer the glsys49.lib library in the distribution zip file to your calculator and store it in port 0, 1 or 2 (e.g., 2 STO). Do a quick reboot with On+C, or just 1652 ATTACH, in order to attach the library. After that the GoferLists functions should be available via the LIB menu or using the command 1652 MENU. For quicker access you might wish to assign \<< 1652 MENU \>> to a key or include it in your custom menu.
Example
As a little example, here is a quick and dirty implementation of Erathosthenes' sieve in RPL. This uses, in particular, GoferLists' Filter function which filters a list with a given predicate. The central routine here is SIEVE which just takes away the first list element P (which already is a prime by virtue of the construction) and invokes itself recursively on the rest of the list after multiples of P have been removed (using Filter):
SIEVE:
\<< IF DUP Null NOT THEN DUP Head \-> P
\<< Tail \<< P MOD 0 \=/ \>> Filter SIEVE P SWAP + \>>
END \>>
PRIMES:
\<< 2 SWAP 1 Seq SIEVE \>>
N PRIMES returns the list of prime numbers up to the given number N. For instance: 50 PRIMES -> { 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 }. Haskell programmers will notice that this is just a more or less literal transcription of the corresponding Haskell program.
Function Overview
Here is a brief rundown of the available functions in the 1.0 version. Most functions are named after their Haskell counterparts (see, e.g., http://haskell.org/hoogle), but some may take different arguments or take arguments in a different order, see the notes below for details. Some functions don't exist in Haskell, but are provided here for convenience. Other functions might work a bit different from their Haskell counterparts, but still serve the same purpose.
Symbol legend: 0/1: truth value, s: string; n: integer (zint or real); x, y, z: any object (sometimes also an arbitrary real or zint); xs, ys, zs: list; xss, yss, zss: list of list; f: arbitrary program; p: predicate (program which returns 0/1 to denote a truth value)
| Function | Stack Diagram | Example |
| All | xs p -> 0/1 | { 1 2 3 } \<< 0 > \>> All -> 1. |
| Any | xs p -> 0/1 | { 1 2 3 } \<< 0 < \>> Any -> 0. |
| Chars | s -> xs | "abc" Chars -> { "a" "b" "c" } |
| Concat | xss -> ys | { { 1 } { 2 3 } } Concat -> { 1 2 3 } |
| Copy | xs n -> ys | { 1 2 3 } 3 Copy -> { 1 2 3 1 2 3 1 2 3 } |
| Delete | xs x -> ys | { 1 2 3 } 2 Delete -> { 1 3 } |
| Diff | xs ys -> zs | { 1 2 3 } { 3 4 5 } Diff -> { 1 2 } |
| Drop | xs n -> ys | { 1 2 3 } 2 Drop -> { 3 } |
| DropWhile | xs p -> ys | { 1 2 3 } \<< 2 < \>> DropWhile -> { 2 3 } |
| Elem | xs x -> 0/1 | { 1 2 3 } 2 Elem -> 1. |
| ElemIndex | xs x -> n | { 1 2 3 } 2 ElemIndex -> 2. |
| Filter | xs p -> ys | { 1 2 3 } \<< 1 > \>> Filter -> { 2 3 } |
| Find | xs p -> x | { 1 2 3 } \<< 1 > \>> Find -> 2 |
| FindIndex | xs p -> n | { 1 2 3 } \<< 1 > \>> FindIndex -> 2. |
| Foldl | xs x f -> ys | { 1 2 3 } 0 \<< + \>> Foldl -> 6 |
| Foldl1 | xs f -> ys | { 1 2 3 } \<< + \>> Foldl1 -> 6 |
| Foldr | xs x f -> ys | { 1 2 3 } 0 \<< + \>> Foldr -> 6 |
| Foldr1 | xs f -> ys | { 1 2 3 } \<< + \>> Foldr1 -> 6 |
| Head | xs -> x | { 1 2 3 } Head -> 1 |
| Init | xs -> ys | { 1 2 3 } Init -> { 1 2 } |
| Inits | xs -> yss | { 1 2 3 } Inits -> { { } { 1 } { 1 2 } { 1 2 3 } } |
| Insert | xs x -> ys | { 1 2 3 } 4 Insert -> { 1 2 3 4 } |
| Intersect | xs ys -> zs | { 1 2 3 } { 3 4 5 } Intersect -> { 3 } |
| Iterate | x f n -> xs | 1 \<< 2 * \>> 10 Iterate -> { 1 2 4 8 16 32 64 128 256 512 } |
| Last | xs -> x | { 1 2 3 } Last -> 3 |
| Length | xs -> n | { 1 2 3 } Length -> 3. |
| Map | xs f -> ys | { 1 2 3 } \<< 3 ^ \>> Map -> { 1 8 27 } |
| Nub | xs -> ys | { 1 2 2 3 2 3 3 } Nub -> { 1 2 3 } |
| Null | xs -> 0/1 | { 1 2 3 } Null -> 0. |
| Product | xs -> x | { 1 2 3 } Product -> 6 |
| Repeat | x n -> xs | 1 5 Repeat -> { 1 1 1 1 1 } |
| Reverse | xs -> ys | { 1 2 3 } Reverse -> { 3 2 1 } |
| Scanl | xs x f -> yss | { 1 2 3 } 0 \<< + \>> Scanl -> { 0 1 3 6 } |
| Scanl1 | xs f -> yss | { 1 2 3 } \<< + \>> Scanl1 -> { 1 3 6 } |
| Scanr | xs x f -> yss | { 1 2 3 } 0 \<< + \>> Scanr -> { 6 5 3 0 } |
| Scanr1 | xs f -> yss | { 1 2 3 } \<< + \>> Scanr1 -> { 6 5 3 } |
| Segs | xs -> yss | { 1 2 3 } Segs -> { { } { 3 } { 2 } { 2 3 } { 1 } { 1 2 } { 1 2 3 } } |
| Seq | x y z -> xs | 1 10 2 Seq -> { 1 3 5 7 9 } |
| Sort | xs p -> ys | { 1 3 2 } \<< < \>> Sort -> { 1 2 3 } |
| Split | xs n -> ys zs | { 1 2 3 } 2 Split -> { 1 2 } { 3 } |
| Strcat | xs -> s | { "a" "b" "c" } Strcat -> "abc" |
| Subs | xs -> yss | { 1 2 3 } Subs -> { { 1 2 3 } { 1 2 } { 1 3 } { 1 } { 2 3 } { 2 } { 3 } { } } |
| Sum | xs -> x | { 1 2 3 } Sum -> 6 |
| Tail | xs -> ys | { 1 2 3 } Tail -> { 2 3 } |
| Tails | xs -> yss | { 1 2 3 } Tails -> { { 1 2 3 } { 2 3 } { 3 } { } } |
| Take | xs n -> ys | { 1 2 3 } 2 Take -> { 1 2 } |
| TakeWhile | xs p -> ys | { 1 2 3 } \<< 2 < \>> TakeWhile -> { 1 } |
| Union | xs ys -> zs | { 1 2 3 } { 3 4 5 } Union -> { 1 2 3 4 5 } |
| Until | x f p -> y | 1 \<< 2 * \>> \<< 1000 > \>> Until -> 1024 |
| Unzip | xss -> xs ys | { {1 A} {2 B} {3 C} } Unzip -> { 1 2 3 } { A B C } |
| Unzip3 | xss -> xs ys zs | { {1 A x} {2 B y} {3 C z} } Unzip3 -> { 1 2 3 } { A B C } { x y z } |
| While | x f p -> xs | 1 \<< 2 * \>> \<< 1000 < \>> While -> { 1 2 4 8 16 32 64 128 256 512 } |
| Zip | xs ys -> xss | { 1 2 3 } { A B C } Zip -> { { 1 A } { 2 B } { 3 C } } |
| Zip3 | xs ys zs -> xss | { 1 2 3 } { A B C } { x y z } Zip3 -> { { 1 A x } { 2 B y } { 3 C z } } |
| ZipWith | xs ys f -> xs' | { 1 2 3 } DUP \<< * \>> ZipWith -> { 1 4 9 } |
| ZipWith3 | xs ys zs f -> xs' | { 1 2 3 } DUP DUP \<< * * \>> ZipWith3 -> { 1 8 27 } |
Notes:
- Chars and Strcat are provided to convert between strings and lists of single character strings. These are not available in Haskell (nor are they needed, since a string already is a list of characters in Haskell), but are provided here for your convenience so that you can manipulate strings using list processing. Note that Strcat can also be used to concatenate an arbitrary list of strings.
- Copy and Split should actually be named Cycle and SplitAt, respectively, but we retained those names for backward compatibility with previous GoferLists versions. Also note that the Diff function (meaning list difference) is implemented by an operator (\\) in Haskell.
- Copy (a.k.a. Haskell's cycle), Iterate and Repeat take an additional integer argument which specifies the number of repetitions or iterations. In Haskell these functions return infinite lists instead. This is possible because of Haskell's lazy evaluation, but of course this wouldn't work in an eager language like RPL.
- In the 1.0 version of GoferLists, Foldl/Foldr now take their arguments in reverse order. This breaks backward compatibility with previous GoferLists versions, but is consistent with other generic list functions like Filter and Map, and makes it possible to "curry" these operations just like you would in Haskell. E.g., concatenating a list of lists can be done using {} \<< + \>> Foldl, just as you'd define concat = foldl (++) [] in Haskell, where the "list of lists" parameter is implicit (the {} a.k.a. [] is the initial empty list from which the accumulation starts). Note that in order to make this work in RPL, the parameters have to be in reverse order, because of RPN. Other higher-order list functions like Filter, Find, Iterate, Map, Scanl/Scanr, Sort etc. work in an analogous fashion.
- Concat, Product, Sum and Strcat are all just special instances of Foldl. They could easily be defined in User RPL, but are already included in the library for your convenience.
- The Seg and Subs function are not in the Haskell library, but work in the same fashion as Inits and Tails. Seg returns the list of all consecutive sublists of a list, while Subs yields the list of *all* (2^N) sublists.
- The Seq function (which is just a simplified frontend for the builtin SEQ) provides a quick means to generate an arithmetic sequence, which can be used as a replacement for Haskell's [x,y..z] construct.
- The Sort function takes an additional order predicate as parameter, so that lists can be sorted according to different criteria. E.g., \<< < \>> Sort and \<< > \>> Sort sorts lists in ascending and descending order, respectively. (Haskell also provides a sortBy function for this purpose, but that function takes a special ordering function instead of a binary predicate as argument.)
- GoferLists also provides a number of operations which implement the usual set operations on lists. The Nub function removes duplicates from a list, so that the resulting list contains each of its members exactly once. The Elem, Insert/Delete, Union/Diff/Intersect functions provide the common set operations: membership test, insert/delete a member, set union, difference and intersection. The Find function works similar to Elem, but looks for an element satisfying the given predicate and returns that element if found, NOVAL otherwise. Both functions also have a variation, ElemIndex/FindIndex, which returns the index of the element in the list (0. if not found) instead.
- Two additional functions are provided to iterate a function starting from an initial value. Until is not actually a list function but is provided for your convenience anyway. It iterates a function starting from the given value and returns the first of the computed values which satisfies the given predicate. E.g., 1 \<< 2 * \>> \<< 1000 > \>> Until returns the first power of 2 which is greater than 1000, i.e., 1024. The "dual" of the Until function is While which returns the list of all iterated values up to the point where the given predicate becomes false. Thus, e.g., 1 \<< 2 * \>> \<< 1000 < \>> While returns the list of all powers of two below 1000, { 1 2 4 8 16 32 64 128 256 512 }. This function is not actually part of the Haskell library, but is equivalent to a combination of Haskell's iterate and takeWhile functions.
- Zip and Zip3 produce a list of lists instead of a list of tuples as in Haskell. The Unzip and Unzip3 functions return two or three result lists on the stack, respectively; in Haskell, these functions return a tuple of lists instead.
Comments (0)
You don't have permission to comment on this page.