Hi there. First time here. Recently started doing Racket. I have a programming related question that I was wondering if someone can help me with. Is this the right channel for those questions or is there another one?

you can ask here

It is kind of long. There is a programming problem that I can do trivially in python or C, but it has taken me several days to do it in Racket. While the racket solution that I ended up with works, I am kind of not happy with it because it is mimicking the same looping and destructive assignment behaviour of the C/python code. Give me a few minutes to post the problem and the python solution so as to give an idea of what needs to be done.

Here is the problem. Given a string like this: ab2[ac] Decode it so as to produce the output: abacac

The code within the [ can itself have nested [ …] which means they need to be decoded first and their output substituted. C code for it is this: int decode (const string &s, int idx, stringstream &str) { int i = idx - 1 ; while (++i < s.length()) { char c = s[i]; if (isalpha (c)) str << c; else if (c == '[') continue; else if (c == ']') break; else if (isdigit (c)) { int n = c - '0'; stringstream str2; int updated_i = decode (s, i + 1, str2); string s2 = str2.str(); for (int j = 0; j < n; j++) str << s2; i = updated_i; } else throw ("some error in string"); } return i; }

Essentially the while loop scans over the string. If it finds an integer - which then must be followed by an opening [, it recurses, and upon finding the closing ], comes out and multiplies the [..] part with the number. The tricky part to get right is to ensure that forward reading must continue from where ] was found. As you can see above, it is done with the idx value being passed into the routine.

My racket solution on the other hand, is quite complicated. #lang racket #\| This second version works. Two core technques: - to break a loop, define own boolean flag break and set it to true - then in the when or unless clause, or with that value to check. - Use own let-loop and ref than relying on for loop because I can't break a for loop myself. - and also scope of those loop variables is not clear and did not work as expected. BAD: Have to use set couple of times Also don't know how to do it yet with list eating ... though I think I can _now_ do it with list eating .. will still need to know when to resume offset at the previous level \|# (define (char->number c) (- (char->integer c) (char->integer #\0))) (define (repeat-sx s x) (define out (open-output-string)) (let loop ([n x]) (if (= n 0) (get-output-string out) (begin (display s out) (loop (sub1 n)))))) (define (decode-via-looping3 s start-i) (define out (open-output-string)) (define N (string-length s)) (define resume-i start-i) (let loop ([i start-i] [break #f]) (unless (or (>= i N) break) (define c (string-ref s i)) ;(printf "~a " c) (cond [(char-alphabetic? c) (display c out) (void)] [(equal? c #\]) (set! resume-i i) (set! break #t) (void)] [(char-numeric? c) (define n (char->number c)) ;(printf "~n >>>>> ~n") (define-values (s2a i2) (decode-via-looping3 s (+ 2 i))) (define s2b (repeat-sx s2a n)) (display s2b out) (set! i i2) ;(printf "~n <<<<< ~n") (void)] [else ;(printf "*** ~a" c) (void)]) (loop (add1 i) break))) (define result (get-output-string out)) (printf "~a: ~a~n" resume-i result) (values result resume-i)) (define (decode s) (define-values (s2 i2) (decode-via-looping3 s 0)) (printf "~n========~n~a: ~a~n" i2 s2)) (decode "a2[Gcc5[Y]dd]vv")

It will print: aGccYYYYYddGccYYYYYddvv

I had to use define-values, set! and simulate the ‘break’ command - all of which I am not quite happy with. Scheme must have some ‘easier’ way to do this problem - specially because recursion seems to be the only way to do this kind of problem.

Also the C version may not be as clean. I am coding up the python version for comparison’s sake.

Incase someone wants to try out the C++ code here are the includes and the main function. #include <string> #include <sstream> #include <iostream> #include <ctype.h> using namespace std; int main(int argc, char *argv[]) { //"ab2[ac]" stringstream str; decode ("abc2[XYZ4[i]]ffft5[vv[8[i]]Q", 0, str); cout << str.str(); return 0; }

so numbers are only allowed before [?

also, what’s the meaning of a [ without a number before it?

yes; i think that sample may be somewhat problematic. Let us simplify it. [ must be preceeded by a number.

We can just use ab2[ac] as an example.

which should give abacac

I am looking for how to do this ‘decoding’ in Racket.

Here is the python code - somewhat cleaner than C++ code. #! /usr/bin/env python def decode_string (s, start_i = 0): out = [] i = start_i while i < len (s): c = s [i] if c.isalpha(): out.append (c) i += 1 elif c.isdigit(): n = ord (c) - ord ('0') assert (s [i + 1] == '[') # and then skip it sub_string, new_i = decode_string (s, i + 2) out.append (n * sub_string) i = new_i elif c == ']': break else: raise Exception ("Error in input") # now outside the while loop out_string = ''.join (out) return (out_string, i + 1) sample2 = "vV2[i]Q" computed2, ignore = decode_string (sample2) print (computed2) And yes, an opening [ must be preceded by a number.

I don’t mean to inundate the chat with messages. I am looking for ‘how to do it in racket/scheme’ kind of answer. Thank you for any guidance.

@aqazi786 If you’re open to using other libraries, here’s a really short solution using the megaparsack package that I think does what you want (with an included test case): #lang racket (require data/applicative data/functor data/monad megaparsack megaparsack/text) (define string-segment/p (or/p (map list->string (many+/p letter/p)) (do [n <- integer/p] (char/p #\[) [str <- string-sequence/p] (char/p #\]) (pure (string-append* (make-list n str)))))) (define string-sequence/p (map string-append* (many/p string-segment/p))) (module+ test (require rackunit) (check-equal? (parse-result! (parse-string string-sequence/p "a2[Gcc5[Y]dd]vv")) "aGccYYYYYddGccYYYYYddvv"))

Disclaimer: megaparsack is my package.

(If you have any questions about that code, do not hesitate to ask!)

Thanks. This is really nice and short. But it is quite some way above my head. I am only familiar with very basic Racket. So lot of code here is very new to me: pure, many/p, many+, do or/p etc. I will have to do some reading and practice to really understand how this code works. Also, down the line using other libraries is fine but for now I want to learn Racket essentials so would need to use just the functionality form the core language / or basic data structures.

One thing though … how do I tell, looking at the code … which methods belong to the package and which are built in. There seem to be several packages included but the code does not seem to be calling methods in all of them.

Though I could be totally wrong.

Yes, megaparsack is a DSL for writing parsers, so most of that code isn’t from core Racket. But there is some documentation here, which has a gentle introduction: http://docs.racket-lang.org/megaparsack/index.html

The high-level idea is that you build up bigger parsers by putting together smaller parsers. So letter/p is a parser that parsers a single letter, and (many+/p letter/p) is a parser that produces one or more letters.

Among various other advantages, one upside to this is that you get nice error messages for bad inputs “for free”: > (parse-result! (parse-string string-sequence/p "bad2string")) string:1:4: parse error unexpected: s expected: '['

In any case, I think I can make an argument that megaparsack is a very Racket-y way of writing parsers, since even though it isn’t built-in, it’s using a domain-specific language to perform a useful task. :)

Thanks for the documentation link. I am going to have to read through it in depth.

I won’t claim this is the only way to solve your problem, or even necessarily the best way—I imagine there are many other ways that I have not even considered—but it is how I would do it. YMMV.

Oh, also: I never answered your question about how to tell which things come from libraries. If you use DrRacket, and you hover your mouse cursor over an identifier, it will tell you where it comes from. You can even right click it and open the documentation.

You can also use the search bar in the top left of the Racket documentation to search for things, but of course if multiple libraries provide things with the same name, then they’ll show up in the results several times.