[racket] Immutable vectors

Konrad,

Check out some of the functional data structures found here:

http://www.ccs.neu.edu/racket/pubs/sfp10-kth.pdf

VLists may be of particular interest in your case.


On Wed, Sep 4, 2013 at 2:37 PM, <users-request at racket-lang.org> wrote:

> Send users mailing list submissions to
>         users at racket-lang.org
>
> To subscribe or unsubscribe via the World Wide Web, visit
>         http://lists.racket-lang.org/users/listinfo
> or, via email, send a message with subject or body 'help' to
>         users-request at racket-lang.org
>
> You can reach the person managing the list at
>         users-owner at racket-lang.org
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of users digest..."
>
>
> [Racket Users list:
>  http://lists.racket-lang.org/users ]
>
>
> Today's Topics:
>
>    1. Re: Immutable vectors (Neil Toronto)
>    2. Macro design question: best way to interpret an expression
>       multiple ways (Neil Toronto)
>    3. Re: Introductory talk on Contracts and Functional Contracts,
>       with most examples in Racket (Daniel Prager)
>    4. Re: Introductory talk on Contracts and Functional Contracts,
>       with most examples in Racket (Robby Findler)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Wed, 04 Sep 2013 14:56:27 -0600
> From: Neil Toronto <neil.toronto at gmail.com>
> To: users at racket-lang.org
> Subject: Re: [racket] Immutable vectors
> Message-ID: <52279E7B.5050406 at gmail.com>
> Content-Type: text/plain; charset=UTF-8; format=flowed
>
> On 09/04/2013 10:28 AM, Konrad Hinsen wrote:
> > For the kind of data I am working with, immutable vectors look like
> > just the right choice: immutable and O(1) element access. However, I
> > am discovering that they are a real pain to work with.
> >
> > Pretty much any vector operation returns a mutable vector: vector-map,
> > vector-drop, vector-split-at, etc. I have to use
> > vector->immutable-vector afterwards to get what I want.  That's a lot
> > of code clutter, and a lot of unnecessary object generation.
> > Getting data from a stream into an immutable vector is the worst: it
> > requires two intermediates: sequence->list, list->vector,
> > vector->immutable-vector.
> >
> > So I am beginning to wonder if immutable vectors are some obsolete
> > feature that is being discouraged. Is there a better choice for an
> > immutable sequence with O(1) element access?
>
> Racket's language design philosophy encourages immutability, so I don't
> see them going away any time soon. Immutable vectors is one area the
> standard library doesn't (currently) meet its design goals, IMO.
>
> FWIW, `vector->immutable-vector' is pretty fast. It's usually the least
> significant part of an O(n) operation. Its two biggest problems are that
> it allocates memory and annoys people.
>
> If you're working in Typed Racket, you might consider using the
> `math/array' library. It provides multidimensional arrays with O(1)
> access, a lot of ways to slice and dice them, and less memory allocation
> (especially if you use nonstrict arrays). They're not necessarily faster
> than vectors, though. Strict immutable arrays are backed by a mutable
> vector, so they allow element access only via a getter, which introduces
> an extra function call.
>
> If you're not in Typed Racket, don't use `math/array' because the
> contract barrier makes element access very slow. But you might be able
> to do something similar: have library functions operate on mutable
> vectors, with user-facing functions accepting and receiving immutable
> vectors, or some more abstract wrapper data type. The `math/matrix'
> library does this, and it works out well enough. A lot of matrix
> operations are fastest when done in-place (e.g. Gaussian elimination),
> but *composing* matrix operations is easiest to reason about when
> matrices are immutable. Many matrix functions copy their arguments'
> elements to a vector, operate destructively on it, and return the result
> wrapped in an array.
>
> Neil ?
>
>
>
> ------------------------------
>
> Message: 2
> Date: Wed, 04 Sep 2013 15:31:23 -0600
> From: Neil Toronto <neil.toronto at gmail.com>
> To: users at racket-lang.org
> Subject: [racket] Macro design question: best way to interpret an
>         expression multiple ways
> Message-ID: <5227A6AB.4080502 at gmail.com>
> Content-Type: text/plain; charset=UTF-8; format=flowed
>
> I have two libraries of combinators meant to be used as targets for a
> language semantics. I'm implementing the semantics using macros; e.g.
>
>     #'(interp (+ 4 5))  =>  #'(((const 4) . &&& . (const 5)) . >>> . add)
>
> where `interp' is a macro and `=>' means macro expansion.
>
> Here's the tricky part. I have to interpret the language using *both*
> combinator libraries, not just one; e.g. I need #'(interp (+ 4 5)) to
> expand to both of these:
>
>    #'(((const/bot 4) . &&&/bot . (const/bot 5)) . >>>/bot . add/bot)
>    #'(((const/pre 4) . &&&/pre . (const/pre 5)) . >>>/pre . add/pre)
>
> I could have #'(interp (+ 4 5)) expand to something like
>
>    #'(list (interp/bot (+ 4 5)) (interp/pre (+ 4 5)))
>
> But expanding twice is terrible manners when the expression contains
> macros.
>
> (Originally, I had super-combinators that did the job of both */bot and
> */pre combinators. These super-combinators were complicated and messy,
> especially when used in recursion, which is why I'm moving the
> "interpret the language two ways" job into the macro system and hoping
> it's nicer. It should also generate faster code, and possibly allow type
> checking on one of the interpretations.)
>
> The best idea I've had so far is to have (interp e) expand to uses of
> generic `&&&' and `>>>' combinators, apply `local-expand', and do a
> syntax tree search-and-replace that does #'&&& => #'&&&/bot, etc. Is
> there another way, though, that doesn't run afoul of macro security?
>
> Neil ?
>
>
> ------------------------------
>
> Message: 3
> Date: Thu, 5 Sep 2013 07:33:10 +1000
> From: Daniel Prager <daniel.a.prager at gmail.com>
> To: Matthias Felleisen <matthias at ccs.neu.edu>
> Cc: users at racket-lang.org
> Subject: Re: [racket] Introductory talk on Contracts and Functional
>         Contracts, with most examples in Racket
> Message-ID:
>         <CAFKxZVVrzzaw87QhkxAN9WjS22hoTV06-dhsg=
> GSe+Z_dV0zmA at mail.gmail.com>
> Content-Type: text/plain; charset="iso-8859-7"
>
> On Wed, Sep 4, 2013 at 7:58 AM, Matthias Felleisen <matthias at ccs.neu.edu>
>  wrote:
>
> You can't.  Sam has had this combination on his todo list for 7 years and
> > he never got around to it. Perhaps I signed his dissertation too early
> :-)
>
>
> I noticed that contract support is missing from TR.  I have, however,
> constructed a roll-my-own contract example with TR, and it would be great
> if Sam (or another!) pushed forward on contract support for TR.
>
> This is from my code base. It is a function that consumes the dimensions of
> > a (functional image) canvas and created a gridded image and an event
> > handler that tells you on which "tile" a user clicked. It is highly real,
> > higher-order, dependent, and yet not difficult to understand.
>
>
> Alas, I am having trouble mentally parsing this, but may still flash it up
> (with acknowledgement!) as a realistic example.
>
> In trying to construct a simpler (yet not easily do-able with static types)
> example I'm running into trouble getting my subcontract right.
>
> I get an "n unbound identifier" error on the penultimate line:
>
> ;; make-indenter: Nat -> (String -> String)
> ;;
> ;; Example: ((make-indenter 4) "foo") -> "    foo"
> ;;
> (define/contract (make-indenter n)
>   (->i ([n natural-number/c])
>        [r (->i ([s string?])
>                [result string?]
>                #:post (s result) (= (string-length result)
>                                     (+ n (string-length s))))])
>   (? (s) (string-append (make-string n #\space) s)))
>
>
> How should I access 'n'?
>
>
> Many thanks
>
> Dan
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: <
> http://lists.racket-lang.org/users/archive/attachments/20130905/37e9e432/attachment-0001.html
> >
>
> ------------------------------
>
> Message: 4
> Date: Wed, 4 Sep 2013 16:37:09 -0500
> From: Robby Findler <robby at eecs.northwestern.edu>
> To: Daniel Prager <daniel.a.prager at gmail.com>
> Cc: Racket Users <users at racket-lang.org>,       Matthias Felleisen
>         <matthias at ccs.neu.edu>
> Subject: Re: [racket] Introductory talk on Contracts and Functional
>         Contracts, with most examples in Racket
> Message-ID:
>         <
> CAL3TdOMETDN4xxymcpxaC5RxJ6oM0M_14-QN-+tSpOD_uNuZzQ at mail.gmail.com>
> Content-Type: text/plain; charset="utf-8"
>
> You need to indicate that the contract on 'r' needs 'n', ie replace "[r
> (->i"  with "[r (n) (->i".
>
> Robby
>
>
> On Wed, Sep 4, 2013 at 4:33 PM, Daniel Prager <daniel.a.prager at gmail.com
> >wrote:
>
> > On Wed, Sep 4, 2013 at 7:58 AM, Matthias Felleisen <matthias at ccs.neu.edu
> >
> >  wrote:
> >
> > You can't.  Sam has had this combination on his todo list for 7 years and
> >> he never got around to it. Perhaps I signed his dissertation too early
> :-)
> >
> >
> > I noticed that contract support is missing from TR.  I have, however,
> > constructed a roll-my-own contract example with TR, and it would be great
> > if Sam (or another!) pushed forward on contract support for TR.
> >
> > This is from my code base. It is a function that consumes the dimensions
> >> of a (functional image) canvas and created a gridded image and an event
> >> handler that tells you on which "tile" a user clicked. It is highly
> real,
> >> higher-order, dependent, and yet not difficult to understand.
> >
> >
> > Alas, I am having trouble mentally parsing this, but may still flash it
> up
> > (with acknowledgement!) as a realistic example.
> >
> > In trying to construct a simpler (yet not easily do-able with static
> > types) example I'm running into trouble getting my subcontract right.
> >
> > I get an "n unbound identifier" error on the penultimate line:
> >
> > ;; make-indenter: Nat -> (String -> String)
> > ;;
> > ;; Example: ((make-indenter 4) "foo") -> "    foo"
> > ;;
> > (define/contract (make-indenter n)
> >   (->i ([n natural-number/c])
> >        [r (->i ([s string?])
> >                [result string?]
> >                #:post (s result) (= (string-length result)
> >                                     (+ n (string-length s))))])
> >    (? (s) (string-append (make-string n #\space) s)))
> >
> >
> > How should I access 'n'?
> >
> >
> > Many thanks
> >
> > Dan
> >
> > ____________________
> >   Racket Users list:
> >   http://lists.racket-lang.org/users
> >
> >
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: <
> http://lists.racket-lang.org/users/archive/attachments/20130904/630811d2/attachment.html
> >
>
> End of users Digest, Vol 97, Issue 12
> *************************************
>



-- 
Talk to you soon,

Scott Klarenbach

PointyHat Software Corp.
www.pointyhat.ca
p 604-568-4280
e scott at pointyhat.ca
200-1575 W. Georgia
Vancouver, BC V6G2V3

_______________________________________
To iterate is human; to recur, divine
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130904/3a61f7ce/attachment-0001.html>