replace?

29 views
Skip to first unread message

Andrew Dabrowski

unread,
Jan 7, 2018, 3:06:33 PM1/7/18
to pure-lang
Is there a replace function for lists, as opposed to the one in the stlvec library, which only works on vecs?

Andrew Dabrowski

unread,
Jan 8, 2018, 4:51:25 PM1/8/18
to pure-lang
I have a vague recollection of having asked this question several years ago and gotten a negative reply. 

If not, can I take this as evidence that Pure is intended more as an interface to other languages (C, Octave) than as a programming language of its own?

Michael Radford

unread,
Jan 8, 2018, 6:29:42 PM1/8/18
to pure...@googlegroups.com
I'm speaking only as a casual user of Pure, but this seems like an odd
question. Pure is very much a programming language of its own.

Replacing the nth element of a list is a one-liner, something like:
replace xs n x = (take (n-1) xs) + (x:(drop n xs));

However, if you often need to do this operation, a list is a very
inefficient data structure because of the need to copy the head of the
list.

I don't see a similar function offered by Haskell, whose standard
library has presumably been labored over by committees for two decades
or so: https://hackage.haskell.org/package/base-4.10.1.0/docs/Data-List.html

Mike
> --
> You received this message because you are subscribed to the Google Groups
> "pure-lang" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to pure-lang+...@googlegroups.com.
> To post to this group, send email to pure...@googlegroups.com.
> Visit this group at https://groups.google.com/group/pure-lang.
> For more options, visit https://groups.google.com/d/optout.

Kurt Pagani

unread,
Jan 8, 2018, 10:01:07 PM1/8/18
to pure...@googlegroups.com
@Mike: well said/written :)

There's also the powerful "reduce_with":
https://puredocs.bitbucket.io/purelib.html?highlight=reduce_with#reduce_with


Example:

kfp@NUC ~
$ pure -i

__ \ | | __| _ \ Pure 0.66 (x86_64-unknown-cygwin)
| | | | | __/ Copyright (c) 2008-2017 by Albert Graef
.__/ \__,_|_| \___| (Type 'help' for help, 'help copying'
_| for license information.)

Loaded prelude from /usr/local/lib/pure/prelude.pure.

> let l=[a,b,c,d];
> reduce_with [a=>x,c=>y] l;
[x,b,y,d]

Andrew Dabrowski

unread,
Jan 8, 2018, 10:30:20 PM1/8/18
to pure...@googlegroups.com, Kurt Pagani
But can this be used to replace the ith element of a list?  Not sure I
understand the doc of reduce_with, but it seems to allow only
replacement reules for the whole list.

Kurt Pagani

unread,
Jan 9, 2018, 12:31:53 PM1/9/18
to pure-lang
Now I see what you mean ;)
IMO terms like "insert" and "replace" are not very welcome in functional languages because they might suggest in-place operations. Moreover, as Mike already told you, they are usually very inefficient when applied to list structures (as lists may be deeply nested).

From the manual:
Note that lists are immutable in Pure (just like most of Pure’s built-in and predefined data structures), so there are no operations which modify lists in-place. E.g., concatenation works as if it was defined recursively by the following rules ...

Replacing the n-th element (or several) of a list effectively means constructing a new list. For instance, replace "5" by "five" in [1..10]:

> let a = [i | i=1..10]; a;
[1,2,3,4,5,6,7,8,9,10]
>  [x|x=[a!i | i=0..3]+[five]+[a!i|i=5..#a-1]];
[1,2,3,4,five,6,7,8,9,10]

There are numerous ways to do this (see  Mike's last post). You can write your own functions and put them into the prelude if you like.


 

Albert Graef

unread,
Jan 10, 2018, 5:28:18 AM1/10/18
to pure...@googlegroups.com
On Sun, Jan 7, 2018 at 9:06 PM, Andrew Dabrowski <unhan...@gmail.com> wrote:
Is there a replace function for lists, as opposed to the one in the stlvec library, which only works on vecs?

Not in the library, but as others have pointed out it's a one-liner if you need it. Just be aware that this kind of operation has O(n) worst-case complexity in functional languages where lists are immutable. So if you need to do a lot of these updates then it's worth looking at alternative data structures. You mentioned stlvec yourself, but there's also dict in the standard library (an immutable associative array a.k.a. hash table) which can be used for such purposes. For instance:

> using dict;
> let xs = dict [i=>i | i = 1..10];
> xs!5;
5
> let ys = insert xs (5=>4711);
> ys!5;
4711

If the size of the list is fixed and you don't mind destructive updates, then you can also use a vector of references (both are built-in Pure data types) and enjoy constant access times. E.g. (note that indices are 0-based here):

> let xs = {ref i | i = 1..10};
> get (xs!4);
5
> put (xs!4) 4711;
4711
> get (xs!4);
4711

That's pretty much as fast as it gets for these kinds of operations in Pure. (For vectors of numbers there are some operations in the library which use less storage and also do bulk updates much faster; alas, both Bitbucket and Github are down for maintenance, so I can't point you to the manual section right now.)

HTH,
Albert

--
Dr. Albert Gr"af
Computer Music Research Group, JGU Mainz, Germany
Email:  agg...@gmail.com
WWW:    https://plus.google.com/+AlbertGraef

Albert Graef

unread,
Jan 10, 2018, 5:44:29 AM1/10/18
to pure...@googlegroups.com
On Mon, Jan 8, 2018 at 10:51 PM, Andrew Dabrowski <unhan...@gmail.com> wrote:
If not, can I take this as evidence that Pure is intended more as an interface to other languages (C, Octave) than as a programming language of its own?

It's both. Think of it like Haskell/ML but with dynamic typing, JIT compilation and a built-in C interface which makes it easy to bridge to the C/C++ world if you want/must. So it works as an interactive scripting language but also as a full-blown FPL in its own right.

Pure's standard library may not be quite as comprehensive as Haskell's or ML's, but let's face it -- even those pale to the likes of Python and JavaScript which seem to have bindings to each and every 3rd party library under the sun. Pure is more on the small-is-beautiful side -- I'm really fond of "small" languages like Lua where you can learn the entire language and its library in a day.

Pure isn't quite as minimalistic as Lua in this regard, however. I think that as you become acquainted with its standard library, you'll notice that a lot of the requisite "batteries" are in fact included. But if you think that something fundamental/important is missing, fine -- submit a bug report (or preferably a pull request) and we can discuss it here. :)

Albert

Albert Graef

unread,
Jan 10, 2018, 6:26:09 AM1/10/18
to pure...@googlegroups.com
On Wed, Jan 10, 2018 at 11:28 AM, Albert Graef <agg...@gmail.com> wrote:
If the size of the list is fixed and you don't mind destructive updates, then you can also use a vector of references (both are built-in Pure data types) and enjoy constant access times. E.g. (note that indices are 0-based here): [...]

I forgot to mention that if your indices are strings or symbols then there's also Pure's built-in record data type which can be used with reference values in pretty much the same way as vectors:

> let xs = map (\(k=>v) -> k => ref v) {a=>1,b=>2,c=>3,d=>4};
> get (xs!c);
3
> put (xs!c) 4711;
4711
> get (xs!c);
4711
> {k => get v | k=>v = xs};
{a=>1,b=>2,c=>4711,d=>4}

That's pretty much as fast as it gets for these kinds of operations in Pure. (For vectors of numbers there are some operations in the library which use less storage and also do bulk updates much faster; alas, both Bitbucket and Github are down for maintenance, so I can't point you to the manual section right now.)

GH is back up again, so here is the manual section I was talking about: https://agraef.github.io/pure-docs/purelib.html#matrix-functions

Matrices/vectors are really the goto data type in Pure if you need an efficient data structure indexed by integers allowing contant-time accesses to its members. Also, bulk update operations like map, matrix comprehensions, etc. are implemented very efficiently. If you need to update single members destructively and you're dealing with huge amounts of numeric data, there also are some low-level operations which enable you to modify such members in-place: https://agraef.github.io/pure-docs/purelib.html#pointer-operations, https://agraef.github.io/pure-docs/purelib.html#pointer-arithmetic. See pure/examples/sieve.pure for an example. These are unsafe and thus the usual caveats apply, but it's easy to wrap them up in your own custom data structure to make them safe. An addon library providing such data structures might actually be a good candidate for a future addition to the standard library. :) Another possibility would be to use GSL operations for that purpose (I've forgotten whether our GSL wrapper already has these...).

Albert

Albert Graef

unread,
Jan 10, 2018, 6:35:37 AM1/10/18
to pure...@googlegroups.com
On Wed, Jan 10, 2018 at 12:26 PM, Albert Graef <agg...@gmail.com> wrote:
See pure/examples/sieve.pure for an example.

 
But this program is so short that I might just as well include it here:

/* The *real* sieve of Erathosthenes. */

// Update an int vector in-place (no checks!).
using pointers;
infix 1000 := ;
def x!i := a = put_int (pointer x+i*SIZEOF_INT) a;

// The sieve. Returns the number of primes up to n.
sieve n = foldl sieve 0 (0..n-1)
// Uncomment this to get the vector of primes instead.
//      $$ filter ((~=)0) x
with
  sieve count i = count+1 when
                    p = i+1; do (\j -> x!j := 0) (i+p:i+2*p..n-1);
                  end if x!i; // x!i is prime
                = count otherwise;
end when
  x = imatrix (1..n); x!0 := 0;
end;
Reply all
Reply to author
Forward
0 new messages