Hey all :slightly_smiling_face: I wrote a function as an exercise which counts occurences of a sublist in a longer list, like so: (occur ’(1 2 3 1 2) ’(1 2)) => 2 (occurences don’t have to be consecutive) (occur ’(1 3 2 1 3) ’(1 2)) => 0 (but all occurences do have to be the entire sequence)

My issue is just that my code feels clunky: (define (occur ls subls) (define sublen (length subls)) (let iter ([ls ls] [count 0]) (let ([lslen (length ls)]) (cond [(> sublen lslen) count] [(equal? subls ls) (+ 1 count)] [(list-prefix? subls ls) (iter (drop ls sublen) (+ 1 count))] [else (iter (drop ls 1) count)]))))

the stack of lets and defines looks ugly, but I couldn’t think how else to express what I wanted to do - that is, prevent cluttering up the main code with (length …) repeatedly. However, the length of the sublist stays the same, so I had to define that separately, and calulate the (changing) length of the other list each iteration of the named let loop.

Furthermore, I try and stay away from explicit recursion when possible, but this is something I couldn’t figure out how to do with map, fold, or any of the more obscure higher-order functions.

Just wanted to get some advice on how others might tackle it, with those things in mind.

Cheers :slightly_smiling_face:

@sydney.lambda It is not necessarily a bad thing to use explicit recursion. However if you want to use the higher-order functions it helps to identify smaller tasks that can be repeated. One useful operation is “Find first occurrence of the sublist and return the remaining elements”.

@sydney.lambda Here is one way to use such an operation:

#lang racket

(define (first-value thunk)
  (call-with-values thunk (λ vs (first vs))))

(define (remove-beyond-sublist xs ys)
  ; Return #f if ys is not a sublist xs,
  ; otherwise return the tail of xs after the first occurrence of ys.
  (cond
    [(empty? xs)          #f]
    [(list-prefix? ys xs) (first-value (λ() (drop-common-prefix xs ys)))]
    [else                 (remove-beyond-sublist (rest xs) ys)]))

(define (occur xs ys)
  (cond
    [(remove-beyond-sublist xs ys) => (λ (xs) (+ 1 (occur xs ys)))]
    [else 0]))

(occur '(1 2 3 1 2) '(1 2))
(occur '(1 3 2 1 3)  '(1 2))

I’d have never thought of that. I figured use of values might help and/or splitting it up into smaller functions, but the way you did is is something I’d have never thought of and is much more elegant, especially => which I always forget exists.

Thank you, that helped a lot! :slightly_smiling_face:

I was only reminded of => because the first version didn’t look pretty :slightly_smiling_face:

So, one use of => seems to be when you’re calling a function (as part of a cond clause predicate/guard) which will not only return #t (or #f otherwise) but will return some kind of transformation which can that be used for subsequent recursion/transformation.

Argh, I couldn’t think how to phrase that, I hope it sort of gets my point across.

Exactly.

Somewhat related to using => in cond: Racket doesn’t “false pun”. (In some other languages, various values might be “falsey” — like an empty list, the number zero, an empty string, etc. But in Racket, all of these are true.) In Racket: #f (a.k.a. #false) is false. Everything else is true.

That annoys me to no end in JavaScript.

In my limited experience using Clojure(Script), it can be annoying when people try to be too clever using nil puns.

Maybe I’m too not-clever, but, “what path will the code take” is not the kind of thing where I appreciate creativity. :slightly_smiling_face:

I think “speculative execution” should be left to Intel and malware authors. :grin:

In Urlang (The JavaScript part) which is more or less a 1–1 mapping between sexp and JS I changed one thing.

(if e0 e1 e2) becomes ((e0===false) ? e2 : e1)

are there decent use-cases for having those sorts of values considered falsey?

the only way I’ve ever seen it used is to avoid explicitly saying things like (racket syntax but not racket of course): (if (empty? ls) … vs (if ls …

which isn’t that big of a deal, especially considering the fact that none of those values “are” false.

I assume the reasoning is that: (positive? 0) => false (not (empty? ls)) => false or something.

The only distinct advantage I’ve ever noticed there is that when false is the same value as the empty list, then it’s like the language already has an option type: The type of a list with no more than one element. Since there are a lot of operations for dealing with lists and booleans, this option type already has good support basically for free. But I find I prefer actually defining a distinct type for that, to better keep track of my intentions.

I think of => as a kind of too-clever punning too. Racket’s "#f or any other value" way of modeling option values breaks down if the thing inside the option value needs to be another option value (or a boolean).

When I said “everything else is true” (besides #f), that wasn’t quite complete. I should have said, “everything else, and nothing, is true”. (if (void) "true" "false") is "true". Even nothing is true. ¯_(ツ)_/¯

Fun fact from R4RS: “It is no longer specified whether the empty list counts as true or as false in conditional expressions.”

@rokitna Yeah, I don’t think I’ve ever used => in cond. I’d be more likely to use match — possibly with app, or often a simple pattern suffices.

For the historically inclined: https://groups.csail.mit.edu/mac/ftpdir/scheme-mail/HTML/rrrs-1988/msg00097.html

@soegaard2 Thanks, that’s interesting.

If you don’t mind Greg, how would you replace the => in: (define (occur xs ys) (cond [(remove-beyond-sublist xs ys) => (λ (xs) (+ 1 (occur xs ys)))] [else 0])) ? At first I thought matching on xs and using the ? pattern that allows you to match predicates could work, but it’s sort of eluding me.

Or did you just mean, for more complex examples you’d avoid => ?

of course, it’s perfectly possible you’d have done something different entirely, but I was curious.

(define (occur xs ys)
  (match (remove-beyond-sublist xs ys)
    [#f  0]
    [xs  (+ 1 (occur xs ys))]))

Gee, I have a talent for over-complicating things if nothing else! Thanks Soegaard :slightly_smiling_face:

Sometimes I like to use match or even match* for problems like this. I can “destructure” lists without using car/cdr or first/rest. It can end up looking like a table, where it’s easy to see each case; especially if you get picky about aligning things. :slightly_smiling_face:

I’m not sure if this is the clearest example, but: #lang racket (define (occur super sub) (let loop ([xs super] [ys sub] [count 0]) (match* [xs ys] [[(list) _ ] count] [[(cons v xs) (list v) ] (loop xs sub (add1 count))] [[(cons v xs) (cons v ys)] (loop xs ys count)] [[(cons _ xs) _ ] (loop xs sub count)]))) (require rackunit) ;; Your examples (check-equal? (occur '(1 2 3 1 2) '(1 2)) 2) (check-equal? (occur '(1 3 2 1 3) '(1 2)) 0) ;; Some more test cases (check-equal? (occur '(1 2 1 2 1 2) '()) 0) (check-equal? (occur '() '()) 0) (check-equal? (occur '(1 2 1 2 1 2) '(1)) 3)

Maybe the named let is a distraction here. Could rewrite the equivalent using a local function named loop or whatever, and, explicitly call it once.

The main point is, we care about two values, xs and ys, and there are four permutations of those we care about.

Wow, thanks for that Greg. I really need to use match more (I use match-let a lot, but that’s about it), it couldn’t have been better suited to my problem.

I’m not sure I understand the third case though. The first is the null case, the second is when the start of super matches sub and so we remove that, increment the count and recur, but I’m unsure of the third case. Wouldn’t it remove the first element from both lists?

Yes. Eventually there is only one element left in the ys. The second case therefore will loop with sub to get the full sub list back.

Hmm, why is it not possible to just do (loop xs sub count) for that case to avoid whittling ys down? (the first test fails with 0) I feel like I’m going to feel silly asking these questions but this is really baffling me for some reason. The inclusion of match just seems to have blown any intuition I had for recursion out of the water :confused: In my head just removing the first element of xs and recurring with sub seems to make sense, but it doesn’t work.

Because the third clause [[(cons v xs) (cons v ys)] ...] only check the first element of the sublist. The rest of the elements need checking too.

To critique my own code: - I don’t love xs and ys as names. - A couple of the clauses rely on the v pattern variable in both left and right patterns. That’s intentional. It matches only for the same value in both patterns. Although that’s an important feature of match patterns, you could argue that’s too subtle for the code to be easy to read?

I feel like the last consideration is always the most important. Rule number one of writing prose is, know your audience. I feel like that’s an undervalued consideration for writing code. When programming in a team, I’d defer to what the team feels is readable vs. too clever or code-golfing.

This is a tangent, but the discussion is about counting occurrences, and I have an amusing story about this, the first one here: https://cs.uwaterloo.ca/~plragde/teachstory.html

I think I’m starting to understand now I’ve slept on it. For some reason I was thinking (list v) meant match the entire list and call it v?! as if there was a … pattern there. Thanks for the help with my questions yesterday everyone, I really appreciate it. I seemed to be having one of those days.