Iterators in Rust return either Some(x) or None, with None being the terminator of the iteration. By explicitly returning the iterator values, Rust's scan gives you the option of terminating the iteration early. Since iterators in Rust are lazy, this could yield a substantial performance improvement for large sequences. Rust is all about performance.
Well, performance and safety. Seriously, if there's any problems with the language they pretty much all come down to "it won't let me write bad code" That's another reason why so many things in Rust return Option values, because they force you to handle null values explicitly. You can't just get by on the assumption that "a null value will just never be passed in," you have to plan for "what should I do if it _does_ happen." Any function that won't always be able to execute has to either error or return an Option.
I wrote one that doesn't use that spooky option syntax s.chars().fold((0, 0), |(max, curr), x| match x { '(' => (if curr == max { max + 1 } else { max }, curr + 1), ')' => (max, curr - 1), _ => (max, curr)} ).0
It has nothing to do with the fact that iterators return `Option`, but you are on the right track. You can actually always end an iterator early using something like `take()` or `take_wile()`. I think what's crucial in this case is that the accumulator is a different type from the return type of the `scan` elements. Hence you may want to abort the sequence early using some condition on the accumulator itself and that is only possible if the return type is `Option`, because a chained iterator would not have access to the accumulator.
One more thing I want to point out: The unwrap_or(0) at the very end has nothing to do with the way scan works. The max function returns an Option because you might apply it to an empty iterator in which case the result is None. The unwrap at the end then either returns the computed maximum or zero, in case the input string had no parentheses.
I saw the membership operator and went "huh, just like from those discrete math classes" and then saw the rest and went "huh, just like they dropped out from discrete math"
APL predate quite all other language except Lisp and C by 20 more years. Doing mapping and general vectors was very nice at that time (it put me so back in time, where I was using IBM 29 punchcard, where APL symbol have to be looked up from a printed card :-) at university where your whole year allocation was 15 minutes of total mainframe time). Nice to see APL survived ! You we’re unfair for Rust because you don’t see the beauty of Maybe(/monad) and how it make such pipes so safe and warranty you a very precise way of dealing with unexpected with a totally expected outcome. You also be very unfair to Ruby, just because you are not expecting your ‘scan’ vs a ‘reduce’ operation, make it an alias and your point is mutt. But it’s nice to see, that once settle on a solution, all langages fall to the same expressiveness. Thanks to the influence on each other in computer langages evolution. Nice demonstration !
You are spot on, actually! Iverson developed the Iverson notation exactly for describing mathematical operations, and he got the Turing award for this. It later became the language APL ("A Programming Language").
For Rust: 1. The scan() function returns an Option because iterators in Rust are potentially infinite, and if the iterator that you're scanning doesn't end, then the scan function needs a way to end the sequence. 2. max() is what causes the Option to be returned at the end, not scan(), and it does so because while iterators can be infinite, they can also be empty. Rust forces you to write code that handles edge cases, which is a good thing, IMHO.
For 1, scan doesn't need to end; it simply produces an iterator of the same length. It's just that someone decided to shove a takeWhile into Rust's scan (or is it filter?).
Doesn't the solution here seem way too complicated and costly - with all those regex's and such? Why not just 1. set temp variable to 0, 2. go through the string one character at a time, add 1 to out temp variable when character is '(', subtract 1 when it is ')' and remember highest value (store highest value in another variable). 3. At string end just return this highest value if your temp variable is 0. If temp variable is different then 0 then input string is not valid
Yup. Would be nicer if a different problem were presented but this is just a demonstration of how to filter and accumulate/fold for those languages. Shame there's no .NET here
Basically the most reasonable solution, I also thought of that because it would actually show you how more realistic code would look like instead of for example the C++20 pipe symbol work flow which has barely been added to the language. Overall I think this is more mean to showcase the built in feature for every language.
Also 2.b if the sum ever reaches -1, then the input string is not valid. But, yeah, I had this in my head the whole time. The way of solving presented here is very nice & mathematical... but if you have really large string (I guess 1GB or bigger) the fact that you have make arrays, and do traversions so many times... ugh. Though maybe the compilers are REALLY smart and can optimize to do basically the same thing that Marek said, though I kind of doubt it.
The solutions use the functional programming paradigm. They might look odd for programmers who only know imperative programming paradigm. I'm new to functional programming, but I see the advantages of fp
@@MarkusBurrer OK, So, based on this, obvious disadvantage of fp must be performance. This is a very simple problem and this approach makes it complicated and extremely costly.
You can use \case in haskell instead of the if-else (also you don't need a filter, just map non-parens to 0) maxDepth = maximum . scanl (+) 0 . map (\case '(' -> 1 ')' -> -1 _ -> 0)
@YuriySyrovetskiy-p7p Lose what performance? You've reimplemented filter, but a branchless add is typically faster than any branch. The real cost is usually access patterns, and every character had to be checked. Besides, if you want to switch scans use scanl', not scanl1. It would be different if you were sending the list of parenthesis somewhere, but Haskell fuses these operations by design.
In your #Clojure impl, the `re-seq` and the `map` steps can be replaced with `(keep {\( 1 \) -1})`. `keep` is a variant of `map` that swallows (omits) `nil`s returned by the mapping fn.
@@abdallahgamal5092 yeah. Clojure maps implement the interface `clojure.lang.IFn`, which means they can be called as functions. In other words, `(get m x)` is the same as `(m x)` for any map `m`. So, you can simplify `#({\( 1\) -1} %)` to `{\( 1\) -1}`.
Here is the F# version using 'choose' which combines filter and map: let maxDepth : string -> int = Seq.choose(function '(' -> Some 1 | ')' -> Some -1 | _ -> None) >> Seq.scan (+) 0 >> Seq.max
Solution can be a bit shorter. This even will run faster if string contains mostly parens, not sure about very long lines with low parens count. let maxDepth : _ seq -> _ = Seq.map(function '(' -> 1 | ')' -> -1 | _ -> 0) >> Seq.scan (+) 0 >> Seq.max
9:10 the Clojure solution can be simplified a great deal. Here's my version: (defn max-depth [s] (->> (reductions #(+ %1 ({\( 1, \) -1} %2 0)) 0 s) (reduce max))) The function we're passing to reductions adds to the accumulator 1 for every opening parenthesis, -1 for every closing parenthesis, and 0 for any other character.
The '&' in Elixir is the capture operator. It is basically syntax sugar to represent a function. It's equivalent to writing the function as: fn (num, acc) -> num + acc end. The &1 and &2 represent the respective parameters.
I think the elixir '.graphemes' makes sense because elixir strings use unicode, maybe something like '.chars' would have been ambiguous, would a char be a grapheme or a char like in C++?
@@ArnabAnimeshDas I think Swift also has something similar, yes it's easier to read, but I still prefer a more precise 'graphemes'. For me char is confusing since in other languages it is a fixed-width type. Also I'm not sure '.chars' in rust actually iterates over graphemes. In the documentation it says the standard lib does not provide that functionality so it's not really comparable.
@@haskell-with-an-extra-chro5605 if we are talking technically, graphemes shouldn't fetch characters. Graphemes may be a collection of characters from a linguistic PoV. Rust fetches unicode characters (not fixed width) when the function chars is invoked.
@@ArnabAnimeshDas I'm no expert on unicode, it is a bit confusing in itself, but I don't know what you mean by 'unicode characters' . Anyway, rust does not iterate over graphemes, that's what I found in the docs.
@@haskell-with-an-extra-chro5605you may use this: crates.io/crates/unicode-segmentation Rust works with utf-8 encoded strings by default unless stated otherwise and chars() function iterates over unicode scalar values.
Nice video. But I think it would be a more interesting video if you can compare the optimal solutions for each language, rather than trying to find the functions that do the same thing in different languages. Each language has their own design philosophy and that's what makes them unique, and that's what we should appreciate the most. That may be a lot of extra work, but the community is happy to help.
Absolutely. In some programming languages, the given definition of nesting depth can be translated almost literally into code. The definition then is the algorithm, and it would lead to a ‘natural’ solution (not necessarily ‘optimal’) in such programming languages. It makes no sense to me to first ‘invent’ another approach/algorithm, and then use a language not designed for imperative programming.
Thanks for the awesome video! For elixir, the ampersand notation is an alternate notation for describing anonymous functions and is not only for use in scan, what you you have as &(&1+&2) is equivalent to having written: fn a, b -> a + b end, the ampersand notation and the shortened if syntax could also have been useful to clean up the function passed to map and avoid having repetitive ends as such: &(if &1 == "(", do: 1, else: -1)
The simplest I can think of is Haskell: maximum . scan (\a c-> if c=="(" then a+1 else if c==")" then a-1 else a) One line. Boom. Time to learn FP my friend. Good luck!
By exploiting the fact that strings are pointers, strings are null terminated, characters can be treated like ints, and the ! operator returns 0 or 1, you can do some terse craziness like this: int maxDepth(char const* s) { int depth=0, max=0; char c; while(c = *s++) { depth += !(c-'(') - !(c-')'); max = MAX(max, depth); } return max; }
@@insertoyouroemail Close! Scan treats a string as a list of characters, so to compare you'll have to use character literals instead of string literals (single quote instead of double quotes around the parenthesis). Also, scan needs an initial value, and it returns a list. Since the assignment is to return the maximum nest depth of the string, you'll want the function to return a numerical value. So a complete "one liner" function would look something like this: maxDepth = maximum . scanl (\a c-> if c=='(' then a+1 else if c==')' then a-1 else a) 0 The signature being the following: maxDepth :: String -> Integer
@@insertoyouroemail If I remove newlines you can do everything in one line. I prefer by making it as unreadable as possible too. :-) But you probably agree that the problem is far too simple for a serious evaluation of different languages or their IDE and debugging systems. A better problem would be something like ray-tracing, or a fluid simulation, with and without rendering on screen. That is because some languages have graphical capabilities in their standard libraries and others don't. In similar sense we may want to add file management too, by declaring the objects/parameters in a file. The algorithms can be very similar and create very different problems in each language. If we don't put too much time in optimising (ray-tracing can use some very complex optimisations), all these all together will give us a good overview of the weaknesses of each language.
Rust has a filter_map function on iterators, and a match statement if you don't like using an if-else like that. .filter_map(|value| match value { '(' => Some(1), ')' => Some(-1), _ => None })
Also known as mapMaybe and case in Haskell and Idris. The LambdaCase extension lets you skip the name, e.g. mapMaybe (\case '(' -> Just 1; ')' -> Just (-1); _ -> Nothing)
I would say that this is a very functional approach to the problem. With languages like C++ and Rust, I would probably have done something way more imperative, and also with only one iteration of the array. Here is some pseudo-code (it's really not ideal to make code on RUclips): int acc = 0, max = 0 For each char c in s: match c with '(' => acc++ ')' => acc-- _ => do nothing if acc>max then max = acc return max
This is the same work, manually interleaved (the automated step is known as loop fusion). let (accN,maxN) = flip foldl' (0,0) (\(acc0,max0) c -> let acc1 = case c of '(' -> succ acc0 ')' -> pred acc0 _ -> acc0 max1 = if acc1>max0 then acc1 else max0 in (acc1, max1)) $ s in maxN maximum . scanl' (+) 0 . map (\c -> case c of '(' -> 1 ')' -> -1 _ -> 0) $ s The compiler can fuse the operations just as well, and understanding the properties of reduce, plus-scan and map, we can parallellize it, exploiting factors like SIMD vectors, multiple cores and out of order execution. Perhaps more significantly, recognizing those patterns lets us see this is possible.
Here you "traverse" the original sequence of characters 3 times which is too much for this kind of problem. But nevermind, the author stated not the optimal solution. Agree that your version is better in terms of readability than author's
@@WuzzupWhitey you're right, not on the original but on the collection that is a result of applying collect. My concern was that Oleg made 3 traversals(if the original string contains only braces this is equivalent to traversing original s 3 times) But making an iterator from the original s solves the problem, as Oleg has already shown in previous answer
I'm not an expert with rust (started learning last year), and I personally never used scan but I have used other methods of iter before. I "Scanned" (heh) the documentation and this is what I think: First off my understanding of most of (if not all) of the iteration method signatures return an Option type. It does this because once a None is returned this will signify the end of the iterator. So you can call collect() after your .map or .scan and it will return a Vec without having to do any unwraps. I believe internally this would be calling iter.next() to return Some(i32) and will unwrap and push these into a Vec until None is returned. I think the confusion comes from your closure function, as you expect it to behave like .map method (and others) you do not return an Option but just the i32 value. My guess here is the Scan method is special and allows you to basically pass a None at any point during the "Scanning of the States" to Stop the iterator early. Try adding a conditional statement to return a None if the acc value is greater than 2 then call collect(). You will see it will drop all values once your acc value hits 3. You could even do it like this: if acc == 3 then return None, even if the next acc value returns a Some(4) we would never see it as collect() stops at the first None it sees Final thing to note: Your unwrap_or(0) isn't actually unwrapping your scan, that is for the max() function. This is because if you call it on an empty iterator / array this will return a None, so you need to tell it how to handle that. Hope this makes sense and helps!
The Rust scan function is a little more verbose, because it is more general: you can return none to stop early, and carry arbitrary state, not just the last element produced in the scan.
You are absolutely correct. In fact this is something I often miss in Haskell. In fact most of the time,when I'm tempted to use `scan` there I would really like having a distinct accumulator. So I assume the Rust folks thought the same thing and designed it (in my opinion) better.
I love the extra functionality you get from it, but I would rather they have "scan" be the same as every other language, and have the current version exist as "manual_scan" or something along those lines.
It's true that it's more general; that's because it's not scan, but a refactoring of a sequential loop capable of implementing scan and linear search. It's a case of manual loop fusion. It targets cases Haskell could already do by map takeWhile scan.
In your solution, you traverse the string 4 times (split, filter, scan, max). Alternatively, you could use a single reduce, and maintain the current and maximum depth. In the below elixir code, the initial splitter is lazy, so each character is only processed once. The other advantage is you can verify the provided string is valid if the current depth is 0 at the end of computation. string |> String.splitter("") |> Enum.reduce(%{current: 0, max: 0}, fn c, acc -> newdepth = case c do "(" -> acc.current + 1 ")" -> acc.current - 1 _ -> acc.current end %{current: newdepth, max: Kernel.max(acc.max, newdepth)} end)
Ironically (considering his demerit for “not part of the standard yet”), I'm pretty sure that the C++20 solution only passes through the string once. He still massively overcomplicated the solution, though.
*a recursive Haskell solution* -- the empty string case: maxDepth "" = 0 -- any string starting with '(' maxDepth ('(':xs) = max (maxDepth xs) (finalDepth xs) -- any other string maxDepth (_:xs) = maxDepth xs -- the depth at the end of a string (should be zero for valid strings) finalDepth = foldr f 0 where f '(' = (-1) f ')' = (+1) -- and as icing on the cake; a way to check a strings validity: isValid = (0 ==) . finalDepth
No need to filter the string, just map non-parenthesis to 0. For example in Haskell: maximum . scanl (+) 0 . map (\case { '(' -> 1; ')' -> -1; _ -> 0 })
I know this video is a little old, but just wanted to say that sometimes we try to hard to shoehorn functional solutions into non-functional languages. I'd have preferred a sightly uglier solution in real C++ than a pretty one in some hypothetical future C++.
I really like those kind of comparison videos. I think it would be nice if you also showed at least one non-functional solution to the problem, so that people can make their mind which style they prefer for that problem. Because I have been programming in a procedural/OO style for quite some time, I personally always have to think procedurally before implementing in a functional way. It requires some translation in my mind.
It feels to me like driving blocks around the city, while you can just take the direct way to the destination. I even think that non-functional solutions are much faster in this case.
@@lordadamson Agreed. But in a Excel style programming environment, or with pipes, functional programming becomes much simpler. I have an old project: Visual Unseen, where I try to combine Excel and DataFlow. www.reddit.com/r/unseen_programming/
I might be biased - having primarily used languages promoting functional code in the past 7 years, but to me the functional solution actually was the first solution to think of and seems much simpler to understand to me.
Literal translation of your algorith into Raku: my $s = '(1+(2*3)+((8)/4))+1'; say [max] [\+] $s.comb.map({ $_ eq '(' ?? 1 !! $_ eq ')' ?? -1 !! Empty }); Empty is the Slip of the empty list and produces a value that vanishes when assigned into a positional container. Thusly, we can filter and map in one go. Please note the irony of Raku tenery operators not needing parantheses when nested (for simple cases).
As there is no requirement for only using functional style, just looping the string char by char, +1 for (, -1 for ), ignore all others, and keep the max value as the result is more elegant and easy to understand. Rust/c/c++ will perform the best. Why make things so complicated?
In elixir & denotes a lambda(anonymous) function where &1 and &2 are positional arguments, same goes for clojure #(+ %1 %2) and other lisps. Speaking of clojure we can replace re-seq by filter over set (filter #{\( \)}) where set is a predicate or by condp in the map expression (map #(condp = % \( 1 \) -1 0)) where = is a predicate [\( 1] [\) -1] test - output pairs and 0 default value.
Two Python solutions, first a more idiomatic one: from itertools import accumulate max_depth = max(accumulate((1 if c == "(" else -1) for c in s if c in "()"), default=0) Second is a more functional one that's probably closer to the spirit of what you're doing here with the other languages: max_depth = max(accumulate(filter(None, map({"(": 1, ")": -1}.get, s))), default=0)
Python and JavaScript are both truly bizarre omissions from this list. const max_depth = s => s .split('') .filter(c => "()".includes(c)) .map(c => c == '(' ? 1 : -1) .reduce( (acc, cur, i) => acc.concat((acc[i-1] || 0) + cur), []) .reduce((a, b) => Math.max(a, b)); The lack of a scan operation, and having to make do with a reduce + accumulator array is felt keenly here. A first pass solution: Array.prototype.scan = function (callback, start) { let res = new Array(this.length); for (let i = 0; i < this.length; i++) { const prev = res[i-1] || start; res[i] = callback(prev, this[i]); } return res; } const max_depth = s => s .split('') .filter(c => "()".includes(c)) .map(c => c == '(' ? 1 : -1) .scan((prev, cur) => prev + cur, 0) .reduce((a, b) => Math.max(a, b));
Is it really fair to use accumulate which isn't builtin? Otherwise, we should use [(prec:=0)]+[(prec:=prec+x)] for x in ] and get: max_depth = max([(prec:=0)]+[(prec:=prec+x) for x in (1 if c == "(" else -1) for c in s if c in "()"])
@@adriengui2646 Also using walrus operator there in a list comprehension is horrendous. Makes the code completely unreadable, IMO, list comprehension should be side effect free.
@@yvrelna I know but I didn't find something better. And that part of my criticism : python's goal is to be clean, but in this case the python's way of doing things is horrendously dirty and unreadable
For Rust solution, providing an explanation of the scan function: 1. Initiate acc to 0, 2. add the 1st element to acc 3. load acc in an iterator 4. move on to the next element and continue It is quite a nifty function if you think about it. you can perform any operation on the elements of the initial array and then perform actions on the final array itself. For example, if you change the function Some(*acc) to Some(2*(*acc)+(*acc)*(*acc)) it will output 8 instead of 2 in the final operator. As for the "option type", it is one of the main reasons why Rust was built in the first place. You use "unwrap" when you know that nothing should go wrong, the compiler can panic whichever way it wants. If you use "expect" you can output your own error message if it fails at that point. You can also choose to deal with errors and successes in all sorts of ways. Basically, "Option type" lets you think about memory safety even if you don't want to.
Wow! APL looks really strange, but also highly intriguing. I’ve never heard of it, thanks for sharing. It doesn’t look like something that I would be very good with, but it’s still interesting.
For Rust, I'd omit the "return" keyword and the filter, use a match instead of an if and directly add the sum up in one step, so I'd get this: pub fn max_depth(s: String) -> i32 { let mut sum: i32 = 0; s.chars() .map(|c|{ sum += match c { '(' => 1, ')' => -1, _ => 0 }; sum }) .max() .unwrap_or(0) }
Thanks for all the replies everyone! I will make a follow up video with all the suggested alternative solutions (F#, JavaScript, etc) and some of the solutions with improved suggestions (Clojure, Elixir, etc). If you have any solutions in other languages you want in the video - post a comment (or reply to the tweet about this video).
I feel inclined to write a solution here, so here's mine, I guess: int depth(const std::string& s) { int max = 0, cur = 0; for (char c : s) max += (cur += (c == '(') - (c == ')')) > max; return max; } Edit: looking at your APL solution, couldn't you have [max]/+/(('('=)-(')'=))s ? I dunno how many parentheses you need, but I'm taking a fork with is_open on the left, and is_close on the right, and subtraction in the middle. That also allows it to be point-free, right?
Quick solution in ocaml let max_depth = String.to_seq %> Seq.filter_map (function '(' -> Some 1 | ')' -> Some (-1) | _ -> None) %> Seq.fold_left (fun (max_d, prev_depth) current -> let cur_depth = prev_depth + current in max max_d cur_depth, cur_depth) (0, 0) %> fst I did a single "scan" of the list so I can collect the max while I'm computing the partial sum, thus avoiding the call to max at the end. It was my gut intuition on how to go with that (before seeing your implementation), but I could also have used a scan and then a max as you do (which is arguably easier to read and also shorter, while a bit less efficient)
yeah, neat but there's really no need to filter anything, instead translate characters to 1, -1 and 0 directly because adding 0 is as good as removing elements.
After removing everything that's not a paren, why not remove all instances of "()" repeatedly, and count how many times until you get an empty string? The first time round removes the two deepest instances, the second removes the remaining nested pair and the third time removes the final, outermost, pair. This will work well for all short expressions with languages like c++, Pascal and so forth
Out of curiosity, I tried this with Java streams, but I can't find a way to do the scan on the stream. Anyone have any ideas? Here's what I came up with: //s is the input as a String int[] arr = s.chars() .filter(c -> "()".indexOf(c) > -1) .map(c -> c == '(' ? 1 : -1) .toArray(); Arrays.parallelPrefix(arr, Integer::sum); return Arrays.stream(arr).max().getAsInt();
I found that if you create a final AtomicInteger first you can then use it in a call to reduce on the stream to do the scan algorithm and that saves a line, but it looks like there's not a way to inline it since streams aren't really meant to hold state this way.
In the C++ version, is that just a bunch of ORs? It seems more like a punch of pipe operations but I'm not familiar with that syntax... What language feature is that?
So apparently this code only works because somewhere he's overriding the pipe to be a function composition help function. The C++ version is secretly missing a TON of code compared to the other versions to look that slick...
This is why I think functional style is just not practical. I can imagine very simple procedural code written in C or C++ which would not only find the maximum depth but also validate that it is VPS. With maximum performance because of early return when invalid VPS state is encountered. Can you do this in any functional language and still keep it fast and readable? I really doubt that.
@@vladimirkraus1438 Thank you. I hadn't read the problem description and only watched the video. I had been wondering if it was a term from Formal Languages that I was supposed to remember.
In elixir, the first ampersand indicates that it's a lambda (this is just a shorthand form, you can always define lambdas using fn), the remaining ampersands denote the n-th argument passed
I'm not an expert in rust but from what I understand the rust implementation of scan allows for separate state and output. Something that is similar to how state space descriptions of dynamic systems in control theory are laid out. In such a system we have some state vector x, an input signal vector u and an output vector y which for the case of a linear system is ruled by the equations x[t+1] = Ax[t] +Bu[t] y[t] = Cx[t] +Du[t] where A, B, C, D are matrices and there is some initial condition x_0 for x. Implementing this in a rust scan would look something like system_output = system_input.scan(x_0, |x, u| { *x = A * x + B * u; Some(C * x + D * u)}) Although in practice I can't see a situation in which you wouldn't like to capture and monitor the state of the system as well as the output unless you try to run a simulation in real time or something like that. The optional in the end could be useful if you have a nonlinear system where there is a risk of dividing by zero or some other undefined thing. To me it seems like a pretty general implementation of the pattern of partial reductions, possibly too general.
From the explanation of the problem it looks like we can simplify it to an iterator over a string, and two variables. One that will increase by 1 every time the current char is '(' and decrease by 1 when it's ')', and the other which will keep the maximum value of the first one. No need for intermediate arrays of numbers or removal of ignored characters. In Scala-like pseudo-code: var max = 0 var counter = 0 str.foreach { case '(' => counter += 1 if (counter > max) max = counter case ')' => counter -= 1 case _ => } max But of course this does not show the standard collections of each language so nicely as the one in your video. (And I absolutely love how the code in the video morphs from one language to the next :D)
For the Elixir solution: 1. Elixir is Unicode by default. If you were guaranteed ASCII input, you could start with `s |> to_charlist |> Enum.filter(fn c -> c == ?( or c == ?) end)`. But that does violate the spirit of building the same solution in each language by skipping the regex. 2. For Enum.scan, you could send the addition function directly: &+/2 3. RE: end end: The alternative is `Enum.map(&(if &1 == "(" do 1 else -1 end))` 3a: You can also use if as a function: Enum.map(&(if(&1 == "(", do: 1, else: -1)))
The `.next()` method on a Rust Iterator returns `None` to indicate that there are no more elements to yield. If the closure for `.scan()` didn't return an Option, it would ALWAYS run the closure on EVERY element in the original iterator. This definition allows you to end iteration early if you determine during your scan that you don't need to look at the rest of the elements.
THat is actually not true. Iterators in Rust are lazy, meaning that even if the function passed to `scan` did not return option you could apply `.take(1)` for instance and it would only produce a single element. I think it is more likely that the idea was that you can early exit from a `scan` using some property computed from of the accumulator, which would otherwise be difficult to do and inefficient
@@JustusAdam well, yeah, that's basically what I was trying to say... You can always end iteration early as the caller, but within the closure that's only possible by returning None.
Used to use Java. Found Scala and started using that and Python in production. Then, I found Rust. When you deal with large amounts of records and your client wants everything quick, you will find that personal preference goes out the window for performance. Rust is a nice mix of speed and ease of use combined with the peace of mind that if you write a bad program, it just won't compile. Very rarely, you will have an issue that the compiler actually doesn't catch. It is kind of idiot proof in that way. It would be kindof interesting to see how Rust uses pointers to see if it is possible to improve program performance by tuning the program for a cache in a large structure. I am sure Rust outperforms most langauges there. It is about equal in performance to C++.
Ruby, Scala and Rust all feature implicit returns. In the scenarios you showed the return keyword was unnecessary and actually bad code style. (In rust you also would have to remove the semicolon for this to work, but close enough) Other than that: interesting video
With Elixir you could do it in one pass through the string with binary pattern matching and a tail recursive function def max_depth(s), do: md(s, {0, 0}) # d = current depth, m = maximum depth found defp md(
Kind of late answer, but I don't see anything in top comments - `scan` want closure returning an option, because it produces new iterator, and returning `None` allows you to early break iterator execution. Also `unwrap` at the end has no relation to `Option` returned in this `scan` - it is because you call `max` on an iterator, and it always returns an `Option` - to have proper value to return in case of empty iterator. If you want to avoid this you may just use single fold: `.fold((0, 0), |(max, prev), x| { let next = prev + x; (std::cmp::max(max, next), next))`.
The keyboard layout which you're currently using doesn't have those keys. But you can use an extended keyboard layout: www.microapl.com/apl/introduction_chapter2.html
When APL was popular (yes, it was popular), there were dedicated computers with their own keyboards. Today, most people write it in emacs and type out names. For example, typing "rho" converts it to "⍴". This is also done with Agda, which isn't as terse as APL but also uses non-Latin letters, including math symbols such as "for-each" (∀) and "exists" (∃). Agda is Haskell-based but primarily used for writing mathematical proofs. (The Common Lisp counterpart is ACL2).
Hilarious! This was the question I use to use when interviewing. I interviewed a C++ Dev for a Java opening and he optimized the performance during the interview.
One thing about the Haskell solution, If you do not like the verbose if and are willing to use some language extensions, then with `LambdaCase` you can combine a lambda with an immediate `case` match and write `map (\case '(' -> 1; _ -> -1)`. You could even roll the filter into it with `concatMap (\case '(' -> [1]; ')' -> [-1]; _ -> [])`
I tried my hand with k, and ended up with |/+\-/"()"=\: I'm honestly surprised how my filter part is much shorter. Does APL lack the each-right/left adverbs?
Graphemes is commonly a thing to use when you have unicode characters. Grapheme meaning "A letter of an alphabet". It takes fully written symbols, compared to single characters as `.chars` would do. Where a full symbol is a letter inclusive super/subscripts like umlauts. As it should be ["ë"] , not ["e", "¨"]. Most `.chars` functions would create the wrong 2nd solution. Grapheme is used as a name specifically to emphasize that it is letter based, not character based. You can also see this differentiation in Ruby, as it includes both.
6:48 Doesn't this code totally miss the "nesting" part in "nesting parenthesis"? Is my following plain old C code functionally equivalent to the Scala example? And yeah, the C function took me less than 3 minutes to write (on my mobile phone, without a code editor), and yeah, it's the throw-away code that I actually would write for a run-once private project, where I'm already sure that all the in-data has correctly nested parentheses (but I'm not a professional programmer, or professional data anything, just an old fashioned computer user that sometimes find it easier, and faster, to write code, than learning to use a complicated app someone else has made). But I wouldn't run somone else, supposedly professional, supposedly generic code, on more realistic data, if I knew it was this horrible. int horriblySloppyDeepestParenNesting( char str[] ) { int max=0, current=0; for( ; *str; str++ ) { max += ( current > max ); current += ( *str == '(' ); current -= ( *str == ')' ); } return max; } The Scala and APL examples, was the only ones that I think I understood fully, but as far as I can tell, the other ones have the same deficit. How would you write something similar to the following two more robust C functions as a functional programmer? int deepestParenNesting( char str[] ) /* UTF-8, or fixed 8 bit, encoded and null terminated string. Return -1 on mismatched parentheses. */ { int max=0, current=0; for( ; *str; str++ ) if( *str == '(' ) current++; else if( *str == ')' ) { if( current max ) max = current; current--; } return ( current == 0 ) ? max : -1; } int deepestParenNesting( char str[] ) /* UTF-8, or fixed 8 bit, encoded and null terminated string. Return negated position in string where first mismatch of parentheses is discovered. */ { int i=0; max=0, current=0; for( ; str[i]; i++ ) if( str[i] == '(' ) current++; else if( str[i] == ')' ) { if( current max ) max = current; current--; } return ( current == 0 ) ? max : -i ; }
For Elixir, if its terseness you're after, you can do better ```elixir def max_depth s do s |> String.replace(~r/[^()]/, "") |> String.graphemes() |> Enum.map(fn "(" -> 1; ")" -> -1 end) |> Enum.scan(&+/2) |> Enum.max() end ``` The function in map uses pattern matching instead of if/else (usually broken down into multiple lines instead of separated by semicolons, but terseness and all that) The function in scan is the same as what you have, but in a more point-free format. & is the capture operator, and functions in Elixir/Erlang/BEAM are identified with their name and their arity, so that is why we have function + with arity 2 (takes 2 arguments). A bit cryptic to some perhaps, but as OP is a fan of APL, this is straight up plain english in comparison.
Or you can take out the string replace, and add one more condition to the map: |> Enum.map(fn "(" -> 1; ")" -> -1; _ -> 0 end) So basically doesn't take out the non-parentheses; it just ignores them in the map.
In Rust you don't need to unwrap because you're getting an array of option. You aren't. It's because max returns an option. The iterator you call max on may be empty so that covers that case.
This a short list of resources: 1. TryAPL.org for a quickstart 2. ruclips.net/user/DyalogConference for free conference videos 3. chat.stackexchange.com/rooms/52405/the-apl-orchard APL Orchard to ask any questions you have 4. dyalog.com for free software download 5. aplwiki.com As for tutorials, I haven't walked through but I have heard this is good (although a bit old school): tutorial.dyalog.com/
My JS solution: Math.max(...input.split("").reduce((c, v) => [...c, c[c.length - 1] += v == "(" ? 1 : v == ")" ? -1 : 0], [0])) With line breaks it can look like this: Math.max( ...input .split("") .reduce( (c, v) => [ ...c, c[c.length - 1] += v == "(" ? 1 : v == ")" ? -1 : 0 ], [0] ) ) I discovered that the "+=" i used in a previous attempt is different from just the addition that would be necessary here. Without the equals, i'd need to wrap the right hand side in parentheses because the addition binds stronger than the equals comparison. This is not the case with plus-equals.
Iterators in Rust return either Some(x) or None, with None being the terminator of the iteration. By explicitly returning the iterator values, Rust's scan gives you the option of terminating the iteration early. Since iterators in Rust are lazy, this could yield a substantial performance improvement for large sequences. Rust is all about performance.
Well, performance and safety. Seriously, if there's any problems with the language they pretty much all come down to "it won't let me write bad code"
That's another reason why so many things in Rust return Option values, because they force you to handle null values explicitly. You can't just get by on the assumption that "a null value will just never be passed in," you have to plan for "what should I do if it _does_ happen." Any function that won't always be able to execute has to either error or return an Option.
I wrote one that doesn't use that spooky option syntax
s.chars().fold((0, 0), |(max, curr), x| match x {
'(' => (if curr == max { max + 1 } else { max }, curr + 1),
')' => (max, curr - 1),
_ => (max, curr)}
).0
@@Sanslife100 That's actually pretty clever, nice work!
It has nothing to do with the fact that iterators return `Option`, but you are on the right track. You can actually always end an iterator early using something like `take()` or `take_wile()`. I think what's crucial in this case is that the accumulator is a different type from the return type of the `scan` elements. Hence you may want to abort the sequence early using some condition on the accumulator itself and that is only possible if the return type is `Option`, because a chained iterator would not have access to the accumulator.
One more thing I want to point out: The unwrap_or(0) at the very end has nothing to do with the way scan works.
The max function returns an Option because you might apply it to an empty iterator in which case the result is None. The unwrap at the end then either returns the computed maximum or zero, in case the input string had no parentheses.
APL looks like someone wanted maths to be a programming language but decided to only keep half of the syntax of everything
I saw the membership operator and went "huh, just like from those discrete math classes" and then saw the rest and went "huh, just like they dropped out from discrete math"
APL predate quite all other language except Lisp and C by 20 more years. Doing mapping and general vectors was very nice at that time (it put me so back in time, where I was using IBM 29 punchcard, where APL symbol have to be looked up from a printed card :-) at university where your whole year allocation was 15 minutes of total mainframe time). Nice to see APL survived !
You we’re unfair for Rust because you don’t see the beauty of Maybe(/monad) and how it make such pipes so safe and warranty you a very precise way of dealing with unexpected with a totally expected outcome.
You also be very unfair to Ruby, just because you are not expecting your ‘scan’ vs a ‘reduce’ operation, make it an alias and your point is mutt.
But it’s nice to see, that once settle on a solution, all langages fall to the same expressiveness. Thanks to the influence on each other in computer langages evolution.
Nice demonstration !
Can you show where the 'half of the syntax' is not kept?
I mean, it was originally designed as a mathematical notation for programs, rather than an actual programming language
You are spot on, actually! Iverson developed the Iverson notation exactly for describing mathematical operations, and he got the Turing award for this. It later became the language APL ("A Programming Language").
For Rust:
1. The scan() function returns an Option because iterators in Rust are potentially infinite, and if the iterator that you're scanning doesn't end, then the scan function needs a way to end the sequence.
2. max() is what causes the Option to be returned at the end, not scan(), and it does so because while iterators can be infinite, they can also be empty.
Rust forces you to write code that handles edge cases, which is a good thing, IMHO.
For 1, scan doesn't need to end; it simply produces an iterator of the same length. It's just that someone decided to shove a takeWhile into Rust's scan (or is it filter?).
Understanding machine code is much easier than reading APL
Consider x+y in machine code....
Machine code is always simpler, only get complex by quantity.
nah man, apl is fantastic. its a refreshing change from java where simple things are complicated
That's just because APL uses such a foreign syntax.
lol good sarcasm
Doesn't the solution here seem way too complicated and costly - with all those regex's and such?
Why not just
1. set temp variable to 0,
2. go through the string one character at a time, add 1 to out temp variable when character is '(', subtract 1 when it is ')' and remember highest value (store highest value in another variable).
3. At string end just return this highest value if your temp variable is 0. If temp variable is different then 0 then input string is not valid
Yup. Would be nicer if a different problem were presented but this is just a demonstration of how to filter and accumulate/fold for those languages. Shame there's no .NET here
Basically the most reasonable solution, I also thought of that because it would actually show you how more realistic code would look like instead of for example the C++20 pipe symbol work flow which has barely been added to the language. Overall I think this is more mean to showcase the built in feature for every language.
Also 2.b if the sum ever reaches -1, then the input string is not valid. But, yeah, I had this in my head the whole time. The way of solving presented here is very nice & mathematical... but if you have really large string (I guess 1GB or bigger) the fact that you have make arrays, and do traversions so many times... ugh. Though maybe the compilers are REALLY smart and can optimize to do basically the same thing that Marek said, though I kind of doubt it.
The solutions use the functional programming paradigm. They might look odd for programmers who only know imperative programming paradigm.
I'm new to functional programming, but I see the advantages of fp
@@MarkusBurrer OK, So, based on this, obvious disadvantage of fp must be performance. This is a very simple problem and this approach makes it complicated and extremely costly.
Absolutely loved the deep dive into APL!
You can use \case in haskell instead of the if-else (also you don't need a filter, just map non-parens to 0)
maxDepth = maximum
. scanl (+) 0
. map (\case '(' -> 1
')' -> -1
_ -> 0)
Only if you've enabled the LambdaCase extension.
@YuriySyrovetskiy-p7p Lose what performance? You've reimplemented filter, but a branchless add is typically faster than any branch. The real cost is usually access patterns, and every character had to be checked. Besides, if you want to switch scans use scanl', not scanl1. It would be different if you were sending the list of parenthesis somewhere, but Haskell fuses these operations by design.
In your #Clojure impl, the `re-seq` and the `map` steps can be replaced with `(keep {\( 1 \) -1})`.
`keep` is a variant of `map` that swallows (omits) `nil`s returned by the mapping fn.
is this because a map implements the IFn interface? kind of like how you can get a key from a map via `({:a "foo"} :a)`?
@@gagansrai8137 yep that's exactly why.
should it look something like that
(defn max-nested-depth
[val]
(->>
val
(keep #({\( 1 \) -1} %))
(reductions +)
(apply max)))
@@abdallahgamal5092 yeah. Clojure maps implement the interface `clojure.lang.IFn`, which means they can be called as functions. In other words, `(get m x)` is the same as `(m x)` for any map `m`. So, you can simplify `#({\( 1\) -1} %)` to `{\( 1\) -1}`.
@@JaihindhReddy Thanks man that was a new nice information for a beginner clojure developer.
Here is the F# version using 'choose' which combines filter and map:
let maxDepth : string -> int =
Seq.choose(function '(' -> Some 1 | ')' -> Some -1 | _ -> None)
>> Seq.scan (+) 0
>> Seq.max
Solution can be a bit shorter. This even will run faster if string contains mostly parens, not sure about very long lines with low parens count.
let maxDepth : _ seq -> _ =
Seq.map(function '(' -> 1 | ')' -> -1 | _ -> 0)
>> Seq.scan (+) 0
>> Seq.max
9:10 the Clojure solution can be simplified a great deal. Here's my version:
(defn max-depth [s]
(->> (reductions #(+ %1 ({\( 1, \) -1} %2 0)) 0 s)
(reduce max)))
The function we're passing to reductions adds to the accumulator 1 for every opening parenthesis, -1 for every closing parenthesis, and 0 for any other character.
Currently on an APL dive thanks to this video, wow love it.
The '&' in Elixir is the capture operator. It is basically syntax sugar to represent a function. It's equivalent to writing the function as:
fn (num, acc) -> num + acc end. The &1 and &2 represent the respective parameters.
I think the elixir '.graphemes' makes sense because elixir strings use unicode, maybe something like '.chars' would have been ambiguous, would a char be a grapheme or a char like in C++?
Rust also uses Unicode though. It uses chars() function for readability.
@@ArnabAnimeshDas I think Swift also has something similar, yes it's easier to read, but I still prefer a more precise 'graphemes'. For me char is confusing since in other languages it is a fixed-width type. Also I'm not sure '.chars' in rust actually iterates over graphemes. In the documentation it says the standard lib does not provide that functionality so it's not really comparable.
@@haskell-with-an-extra-chro5605 if we are talking technically, graphemes shouldn't fetch characters. Graphemes may be a collection of characters from a linguistic PoV. Rust fetches unicode characters (not fixed width) when the function chars is invoked.
@@ArnabAnimeshDas I'm no expert on unicode, it is a bit confusing in itself, but I don't know what you mean by 'unicode characters' . Anyway, rust does not iterate over graphemes, that's what I found in the docs.
@@haskell-with-an-extra-chro5605you may use this: crates.io/crates/unicode-segmentation
Rust works with utf-8 encoded strings by default unless stated otherwise and chars() function iterates over unicode scalar values.
Nice video.
But I think it would be a more interesting video if you can compare the optimal solutions for each language, rather than trying to find the functions that do the same thing in different languages. Each language has their own design philosophy and that's what makes them unique, and that's what we should appreciate the most.
That may be a lot of extra work, but the community is happy to help.
Absolutely. In some programming languages, the given definition of nesting depth can be translated almost literally into code. The definition then is the algorithm, and it would lead to a ‘natural’ solution (not necessarily ‘optimal’) in such programming languages. It makes no sense to me to first ‘invent’ another approach/algorithm, and then use a language not designed for imperative programming.
Thanks for the awesome video! For elixir, the ampersand notation is an alternate notation for describing anonymous functions and is not only for use in scan, what you you have as &(&1+&2) is equivalent to having written: fn a, b -> a + b end, the ampersand notation and the shortened if syntax could also have been useful to clean up the function passed to map and avoid having repetitive ends as such: &(if &1 == "(", do: 1, else: -1)
Heh, that's what I was going to recommend: gist.github.com/jc00ke/1e17d6e160a75dc303c7f50e500cda03#file-0210_problem_1-ex
I know that is a bit late, but &Kernel.+/2 its an option too
APL looks so interesting! Great video, I really appreciate the quality!
If you want to get into APL, I recommend the APL Wiki, and APL Orchard on StackExchange
I love APL. Such a cool language with a very unique history.
APL reminds me a lot of numpy with all those vector operations and boolean arrays
That is the simplest problem I can think of.
Just one simple loop.
int GetMax(char *str){
int max= 0; int depth=0;
for ( int i=0; i
The simplest I can think of is Haskell:
maximum . scan (\a c-> if c=="(" then a+1 else if c==")" then a-1 else a)
One line. Boom. Time to learn FP my friend. Good luck!
By exploiting the fact that strings are pointers, strings are null terminated, characters can be treated like ints, and the ! operator returns 0 or 1, you can do some terse craziness like this:
int maxDepth(char const* s)
{
int depth=0, max=0;
char c;
while(c = *s++) {
depth += !(c-'(') - !(c-')');
max = MAX(max, depth);
}
return max;
}
@@insertoyouroemail Close! Scan treats a string as a list of characters, so to compare you'll have to use character literals instead of string literals (single quote instead of double quotes around the parenthesis). Also, scan needs an initial value, and it returns a list. Since the assignment is to return the maximum nest depth of the string, you'll want the function to return a numerical value. So a complete "one liner" function would look something like this:
maxDepth = maximum . scanl (\a c-> if c=='(' then a+1 else if c==')' then a-1 else a) 0
The signature being the following:
maxDepth :: String -> Integer
@@johnwarren6966 Yes! I blame the RUclips comment field for being a less than ideal Haskell IDE!
@@insertoyouroemail If I remove newlines you can do everything in one line. I prefer by making it as unreadable as possible too. :-) But you probably agree that the problem is far too simple for a serious evaluation of different languages or their IDE and debugging systems. A better problem would be something like ray-tracing, or a fluid simulation, with and without rendering on screen. That is because some languages have graphical capabilities in their standard libraries and others don't. In similar sense we may want to add file management too, by declaring the objects/parameters in a file. The algorithms can be very similar and create very different problems in each language. If we don't put too much time in optimising (ray-tracing can use some very complex optimisations), all these all together will give us a good overview of the weaknesses of each language.
Rust has a filter_map function on iterators, and a match statement if you don't like using an if-else like that.
.filter_map(|value| match value { '(' => Some(1), ')' => Some(-1), _ => None })
he clearly has no idea what he is doing...
Also known as mapMaybe and case in Haskell and Idris. The LambdaCase extension lets you skip the name, e.g.
mapMaybe (\case '(' -> Just 1; ')' -> Just (-1); _ -> Nothing)
I would say that this is a very functional approach to the problem.
With languages like C++ and Rust, I would probably have done something way more imperative, and also with only one iteration of the array. Here is some pseudo-code (it's really not ideal to make code on RUclips):
int acc = 0, max = 0
For each char c in s:
match c with
'(' => acc++
')' => acc--
_ => do nothing
if acc>max then max = acc
return max
Yes, the author is just a fan of the functional approach.
This is the same work, manually interleaved (the automated step is known as loop fusion).
let (accN,maxN) = flip foldl' (0,0) (\(acc0,max0) c ->
let
acc1 = case c of
'(' -> succ acc0
')' -> pred acc0
_ -> acc0
max1 = if acc1>max0 then acc1 else max0
in (acc1, max1)) $ s
in maxN
maximum . scanl' (+) 0 . map (\c -> case c of
'(' -> 1
')' -> -1
_ -> 0) $ s
The compiler can fuse the operations just as well, and understanding the properties of reduce, plus-scan and map, we can parallellize it, exploiting factors like SIMD vectors, multiple cores and out of order execution. Perhaps more significantly, recognizing those patterns lets us see this is possible.
For scala it's
def maxDepth(s: String) = s.collect{case '(' => 1 ; case ')' => -1}.scanLeft(0)(_ + _).max
Here you "traverse" the original sequence of characters 3 times which is too much for this kind of problem. But nevermind, the author stated not the optimal solution. Agree that your version is better in terms of readability than author's
@@mbesida It's just for shortness, s.iterator.collect{case '(' => 1 ; case ')' => -1}.scanLeft(0)(_ + _).max is a single traverse solution
@@mbesida Why on original? Isn't scanLeft operates on the output of the collect?
@@WuzzupWhitey you're right, not on the original but on the collection that is a result of applying collect. My concern was that Oleg made 3 traversals(if the original string contains only braces this is equivalent to traversing original s 3 times) But making an iterator from the original s solves the problem, as Oleg has already shown in previous answer
I'm not an expert with rust (started learning last year), and I personally never used scan but I have used other methods of iter before. I "Scanned" (heh) the documentation and this is what I think:
First off my understanding of most of (if not all) of the iteration method signatures return an Option type. It does this because once a None is returned this will signify the end of the iterator.
So you can call collect() after your .map or .scan and it will return a Vec without having to do any unwraps. I believe internally this would be calling iter.next() to return Some(i32) and will unwrap and push these into a Vec until None is returned.
I think the confusion comes from your closure function, as you expect it to behave like .map method (and others) you do not return an Option but just the i32 value.
My guess here is the Scan method is special and allows you to basically pass a None at any point during the "Scanning of the States"
to Stop the iterator early. Try adding a conditional statement to return a None if the acc value is greater than 2 then call collect(). You will see it will drop all values once your acc value hits 3. You could even do it like this: if acc == 3 then return None, even if the next acc value returns a Some(4) we would never see it as collect() stops at the first None it sees
Final thing to note: Your unwrap_or(0) isn't actually unwrapping your scan, that is for the max() function. This is because if you call it on an empty iterator / array this will return a None, so you need to tell it how to handle that.
Hope this makes sense and helps!
The Rust scan function is a little more verbose, because it is more general: you can return none to stop early, and carry arbitrary state, not just the last element produced in the scan.
You are absolutely correct. In fact this is something I often miss in Haskell. In fact most of the time,when I'm tempted to use `scan` there I would really like having a distinct accumulator. So I assume the Rust folks thought the same thing and designed it (in my opinion) better.
I love the extra functionality you get from it, but I would rather they have "scan" be the same as every other language, and have the current version exist as "manual_scan" or something along those lines.
It's true that it's more general; that's because it's not scan, but a refactoring of a sequential loop capable of implementing scan and linear search. It's a case of manual loop fusion. It targets cases Haskell could already do by map takeWhile scan.
In your solution, you traverse the string 4 times (split, filter, scan, max). Alternatively, you could use a single reduce, and maintain the current and maximum depth. In the below elixir code, the initial splitter is lazy, so each character is only processed once. The other advantage is you can verify the provided string is valid if the current depth is 0 at the end of computation.
string
|> String.splitter("")
|> Enum.reduce(%{current: 0, max: 0}, fn c, acc ->
newdepth = case c do
"(" -> acc.current + 1
")" -> acc.current - 1
_ -> acc.current
end
%{current: newdepth, max: Kernel.max(acc.max, newdepth)}
end)
wow I'm glad someone else said it
thanks
Ironically (considering his demerit for “not part of the standard yet”), I'm pretty sure that the C++20 solution only passes through the string once. He still massively overcomplicated the solution, though.
Which solution? Several of the languages shown perform loop fusion and will merge the steps into one traversal.
Just install bracket pair colorizer and boom, done
*a recursive Haskell solution*
-- the empty string case:
maxDepth "" = 0
-- any string starting with '('
maxDepth ('(':xs) = max (maxDepth xs) (finalDepth xs)
-- any other string
maxDepth (_:xs) = maxDepth xs
-- the depth at the end of a string (should be zero for valid strings)
finalDepth = foldr f 0
where f '(' = (-1)
f ')' = (+1)
-- and as icing on the cake; a way to check a strings validity:
isValid = (0 ==) . finalDepth
Thanks for sharing! The APL explanation was fascinating. APL, J and the family are big time on my list to study further.
In Haskell, `bool` can provide you the more concise ternary you’re looking for.
No need to filter the string, just map non-parenthesis to 0. For example in Haskell: maximum . scanl (+) 0 . map (\case { '(' -> 1; ')' -> -1; _ -> 0 })
This problem is a great showcase of functional programming - it has a map, a filter, a fold and a scan, everything you need to introduce a beginner
I know this video is a little old, but just wanted to say that sometimes we try to hard to shoehorn functional solutions into non-functional languages. I'd have preferred a sightly uglier solution in real C++ than a pretty one in some hypothetical future C++.
A small one about scala: don’t use return. Just remove it here. Curly braces can go too here.
On another video should look at execution efficiency comparison.
I really like those kind of comparison videos. I think it would be nice if you also showed at least one non-functional solution to the problem, so that people can make their mind which style they prefer for that problem. Because I have been programming in a procedural/OO style for quite some time, I personally always have to think procedurally before implementing in a functional way. It requires some translation in my mind.
It feels to me like driving blocks around the city, while you can just take the direct way to the destination.
I even think that non-functional solutions are much faster in this case.
@@zyxzevn Eh, it depends on how clever your compiler is
Our brains are not built for functional programming. I don't like mental gymnastics. I like simple and straight forward.
@@lordadamson Agreed. But in a Excel style programming environment, or with pipes, functional programming becomes much simpler.
I have an old project: Visual Unseen, where I try to combine Excel and DataFlow.
www.reddit.com/r/unseen_programming/
I might be biased - having primarily used languages promoting functional code in the past 7 years, but to me the functional solution actually was the first solution to think of and seems much simpler to understand to me.
4:57 what is the use of '|' s there? also how the functions are being called wihtout a "." (dot)?
I did not know but that beatu of language: APL. Great explanation. You have inspired me too look at that language. Thanks!
Literal translation of your algorith into Raku:
my $s = '(1+(2*3)+((8)/4))+1';
say [max] [\+] $s.comb.map({ $_ eq '(' ?? 1 !! $_ eq ')' ?? -1 !! Empty });
Empty is the Slip of the empty list and produces a value that vanishes when assigned into a positional container. Thusly, we can filter and map in one go.
Please note the irony of Raku tenery operators not needing parantheses when nested (for simple cases).
@ghldex4772 The sqare brackets of `[max]` seem to be unnecessary.
I haven't got the faintest idea of what is going on but this is fucking impressive. I am really impressed. Good job, mate.
Nice video, if you will do similar could you include F# in the list of languages?
As there is no requirement for only using functional style, just looping the string char by char, +1 for (, -1 for ), ignore all others, and keep the max value as the result is more elegant and easy to understand. Rust/c/c++ will perform the best. Why make things so complicated?
In elixir & denotes a lambda(anonymous) function where &1 and &2 are positional arguments, same goes for clojure #(+ %1 %2) and other lisps.
Speaking of clojure we can replace re-seq by filter over set (filter #{\( \)}) where set is a predicate or by condp in the map expression (map #(condp = % \( 1 \) -1 0))
where = is a predicate [\( 1] [\) -1] test - output pairs and 0 default value.
Those transitions tho... beautiful.
Powerpoint character morph transition
Two Python solutions, first a more idiomatic one:
from itertools import accumulate
max_depth = max(accumulate((1 if c == "(" else -1) for c in s if c in "()"), default=0)
Second is a more functional one that's probably closer to the spirit of what you're doing here with the other languages:
max_depth = max(accumulate(filter(None, map({"(": 1, ")": -1}.get, s))), default=0)
Python and JavaScript are both truly bizarre omissions from this list.
const max_depth = s =>
s
.split('')
.filter(c => "()".includes(c))
.map(c => c == '(' ? 1 : -1)
.reduce(
(acc, cur, i) => acc.concat((acc[i-1] || 0) + cur),
[])
.reduce((a, b) => Math.max(a, b));
The lack of a scan operation, and having to make do with a reduce + accumulator array is felt keenly here. A first pass solution:
Array.prototype.scan = function (callback, start) {
let res = new Array(this.length);
for (let i = 0; i < this.length; i++) {
const prev = res[i-1] || start;
res[i] = callback(prev, this[i]);
}
return res;
}
const max_depth = s =>
s
.split('')
.filter(c => "()".includes(c))
.map(c => c == '(' ? 1 : -1)
.scan((prev, cur) => prev + cur, 0)
.reduce((a, b) => Math.max(a, b));
Is it really fair to use accumulate which isn't builtin?
Otherwise, we should use [(prec:=0)]+[(prec:=prec+x)] for x in ] and get:
max_depth = max([(prec:=0)]+[(prec:=prec+x) for x in (1 if c == "(" else -1) for c in s if c in "()"])
@@adriengui2646 Whether it's fair or not is up to you. For me, anything from the standard library is fair game.
@@adriengui2646 Also using walrus operator there in a list comprehension is horrendous. Makes the code completely unreadable, IMO, list comprehension should be side effect free.
@@yvrelna I know but I didn't find something better.
And that part of my criticism : python's goal is to be clean, but in this case the python's way of doing things is horrendously dirty and unreadable
For Rust solution, providing an explanation of the scan function:
1. Initiate acc to 0,
2. add the 1st element to acc
3. load acc in an iterator
4. move on to the next element and continue
It is quite a nifty function if you think about it. you can perform any operation on the elements of the initial array and then perform actions on the final array itself.
For example, if you change the function Some(*acc) to Some(2*(*acc)+(*acc)*(*acc)) it will output 8 instead of 2 in the final operator.
As for the "option type", it is one of the main reasons why Rust was built in the first place. You use "unwrap" when you know that nothing should go wrong, the compiler can panic whichever way it wants. If you use "expect" you can output your own error message if it fails at that point. You can also choose to deal with errors and successes in all sorts of ways.
Basically, "Option type" lets you think about memory safety even if you don't want to.
“except” or “expect”
@@michaelwu6914 edited. thanx. :)
Also fun fact which I forgot to mention, you don't need to use filter and map if you use booleans in scan function.
0x0.st/iDX9.rs
Wow! APL looks really strange, but also highly intriguing. I’ve never heard of it, thanks for sharing. It doesn’t look like something that I would be very good with, but it’s still interesting.
For Rust, I'd omit the "return" keyword and the filter, use a match instead of an if and directly add the sum up in one step, so I'd get this:
pub fn max_depth(s: String) -> i32 {
let mut sum: i32 = 0;
s.chars()
.map(|c|{ sum += match c { '(' => 1, ')' => -1, _ => 0 }; sum })
.max()
.unwrap_or(0)
}
After that APL example, I really want to see the Perl solution (for entertainment purposes)
Thanks for all the replies everyone! I will make a follow up video with all the suggested alternative solutions (F#, JavaScript, etc) and some of the solutions with improved suggestions (Clojure, Elixir, etc). If you have any solutions in other languages you want in the video - post a comment (or reply to the tweet about this video).
Python is a popular language and should be considered.
You probably know this but you can omit the return statement (and semicolon) in Rust. Feels more idiomatic in a function like this.
I feel inclined to write a solution here, so here's mine, I guess:
int depth(const std::string& s)
{
int max = 0, cur = 0;
for (char c : s)
max += (cur += (c == '(') - (c == ')')) > max;
return max;
}
Edit: looking at your APL solution, couldn't you have [max]/+/(('('=)-(')'=))s ?
I dunno how many parentheses you need, but I'm taking a fork with is_open on the left, and is_close on the right, and subtraction in the middle.
That also allows it to be point-free, right?
Unusually concise for C++, and branchless too (disregarding the loop).
Quick solution in ocaml
let max_depth =
String.to_seq
%> Seq.filter_map (function '(' -> Some 1 | ')' -> Some (-1) | _ -> None)
%> Seq.fold_left
(fun (max_d, prev_depth) current ->
let cur_depth = prev_depth + current in
max max_d cur_depth, cur_depth)
(0, 0)
%> fst
I did a single "scan" of the list so I can collect the max while I'm computing the partial sum, thus avoiding the call to max at the end. It was my gut intuition on how to go with that (before seeing your implementation), but I could also have used a scan and then a max as you do (which is arguably easier to read and also shorter, while a bit less efficient)
5:00 what is the syntax is used? Thanks you.
The Scala solution is beautiful, elegant, and easy to read and write. It was my number 1 by far.
I was once told that the idiomatic way in Haskell would be:
filter (`elem` "()")
great video! Thanks.
yeah, neat but there's really no need to filter anything, instead translate characters to 1, -1 and 0 directly because adding 0 is as good as removing elements.
Dunno if anyone has said this yet, but & is syntactic sugar for anonymous functions in Elixir. &(&1+&2) is basically fn (p1, p2) -> p1 + p2 end
In Rust, I don't understand why you filter and then map. Can't you flatMap with "(" == Some(1), ")" == Some(-1) and the rest being None?
After removing everything that's not a paren, why not remove all instances of "()" repeatedly, and count how many times until you get an empty string? The first time round removes the two deepest instances, the second removes the remaining nested pair and the third time removes the final, outermost, pair. This will work well for all short expressions with languages like c++, Pascal and so forth
Out of curiosity, I tried this with Java streams, but I can't find a way to do the scan on the stream. Anyone have any ideas? Here's what I came up with:
//s is the input as a String
int[] arr = s.chars()
.filter(c -> "()".indexOf(c) > -1)
.map(c -> c == '(' ? 1 : -1)
.toArray();
Arrays.parallelPrefix(arr, Integer::sum);
return Arrays.stream(arr).max().getAsInt();
I found that if you create a final AtomicInteger first you can then use it in a call to reduce on the stream to do the scan algorithm and that saves a line, but it looks like there's not a way to inline it since streams aren't really meant to hold state this way.
damn, you should do some APL tutorials
In the C++ version, is that just a bunch of ORs? It seems more like a punch of pipe operations but I'm not familiar with that syntax... What language feature is that?
So apparently this code only works because somewhere he's overriding the pipe to be a function composition help function. The C++ version is secretly missing a TON of code compared to the other versions to look that slick...
This is why I think functional style is just not practical. I can imagine very simple procedural code written in C or C++ which would not only find the maximum depth but also validate that it is VPS. With maximum performance because of early return when invalid VPS state is encountered. Can you do this in any functional language and still keep it fast and readable? I really doubt that.
What is "VPS"?
@@asongfromunderthefloorboards VPS = Valid Parentheses String. it is described in the "problem link" below the video.
@@vladimirkraus1438 Thank you. I hadn't read the problem description and only watched the video. I had been wondering if it was a term from Formal Languages that I was supposed to remember.
Shouldn’t you also invalidate any array that doesn’t end in 0?
In elixir, the first ampersand indicates that it's a lambda (this is just a shorthand form, you can always define lambdas using fn), the remaining ampersands denote the n-th argument passed
I'm not an expert in rust but from what I understand the rust implementation of scan allows for separate state and output. Something that is similar to how state space descriptions of dynamic systems in control theory are laid out.
In such a system we have some state vector x, an input signal vector u and an output vector y which for the case of a linear system is ruled by the equations
x[t+1] = Ax[t] +Bu[t]
y[t] = Cx[t] +Du[t]
where A, B, C, D are matrices and there is some initial condition x_0 for x.
Implementing this in a rust scan would look something like
system_output = system_input.scan(x_0, |x, u| { *x = A * x + B * u; Some(C * x + D * u)})
Although in practice I can't see a situation in which you wouldn't like to capture and monitor the state of the system as well as the output unless you try to run a simulation in real time or something like that.
The optional in the end could be useful if you have a nonlinear system where there is a risk of dividing by zero or some other undefined thing.
To me it seems like a pretty general implementation of the pattern of partial reductions, possibly too general.
I didn't know about scan. But there is also fold, which is probably what you'd want to use.
how about performance? which solution was fastest to run?
do they sell a special keyboard with APL?
Ruby example is incorrect, because acc.first returns nil for first iteration so nil + 1 -> undefined method
I used acc.last and defaulted to 0 - gist.github.com/jc00ke/1e17d6e160a75dc303c7f50e500cda03#file-0210_problem_1-rb-L6
Seems it ‘injected/reduced’ with a 0 initial value for the accumulator
From the explanation of the problem it looks like we can simplify it to an iterator over a string, and two variables. One that will increase by 1 every time the current char is '(' and decrease by 1 when it's ')', and the other which will keep the maximum value of the first one. No need for intermediate arrays of numbers or removal of ignored characters. In Scala-like pseudo-code:
var max = 0
var counter = 0
str.foreach {
case '(' =>
counter += 1
if (counter > max) max = counter
case ')' =>
counter -= 1
case _ =>
}
max
But of course this does not show the standard collections of each language so nicely as the one in your video. (And I absolutely love how the code in the video morphs from one language to the next :D)
For the Elixir solution:
1. Elixir is Unicode by default. If you were guaranteed ASCII input, you could start with `s |> to_charlist |> Enum.filter(fn c -> c == ?( or c == ?) end)`. But that does violate the spirit of building the same solution in each language by skipping the regex.
2. For Enum.scan, you could send the addition function directly: &+/2
3. RE: end end: The alternative is `Enum.map(&(if &1 == "(" do 1 else -1 end))`
3a: You can also use if as a function: Enum.map(&(if(&1 == "(", do: 1, else: -1)))
Or Enum.map(fn
"(" -> 1
_ -> -1
end
;-)
Awesome video! Also slick transitions
dyalog apl is SWEEEET
The `.next()` method on a Rust Iterator returns `None` to indicate that there are no more elements to yield. If the closure for `.scan()` didn't return an Option, it would ALWAYS run the closure on EVERY element in the original iterator. This definition allows you to end iteration early if you determine during your scan that you don't need to look at the rest of the elements.
THat is actually not true. Iterators in Rust are lazy, meaning that even if the function passed to `scan` did not return option you could apply `.take(1)` for instance and it would only produce a single element. I think it is more likely that the idea was that you can early exit from a `scan` using some property computed from of the accumulator, which would otherwise be difficult to do and inefficient
@@JustusAdam well, yeah, that's basically what I was trying to say... You can always end iteration early as the caller, but within the closure that's only possible by returning None.
@@KevinDay Well you said it would run the closure on every element, suggesting eager evaluation which is incorrect or at least ambiguous.
@@JustusAdam You're right, my wording was imprecise. Sorry.
@@KevinDay No worries, an easy mistake to make. ;)
The Elixir's func is called "graphemes" because it is Unicode-safe and UTF chars are called graphemes
Used to use Java. Found Scala and started using that and Python in production. Then, I found Rust. When you deal with large amounts of records and your client wants everything quick, you will find that personal preference goes out the window for performance. Rust is a nice mix of speed and ease of use combined with the peace of mind that if you write a bad program, it just won't compile. Very rarely, you will have an issue that the compiler actually doesn't catch. It is kind of idiot proof in that way. It would be kindof interesting to see how Rust uses pointers to see if it is possible to improve program performance by tuning the program for a cache in a large structure. I am sure Rust outperforms most langauges there. It is about equal in performance to C++.
Ruby, Scala and Rust all feature implicit returns. In the scenarios you showed the return keyword was unnecessary and actually bad code style. (In rust you also would have to remove the semicolon for this to work, but close enough)
Other than that: interesting video
With Elixir you could do it in one pass through the string with binary pattern matching and a tail recursive function
def max_depth(s), do: md(s, {0, 0})
# d = current depth, m = maximum depth found
defp md(
If I'm not mistaken you could write ((flip elem) "()") of the haskell solution as ("()" `elem`) if you didn't know yet :)
Kind of late answer, but I don't see anything in top comments - `scan` want closure returning an option, because it produces new iterator, and returning `None` allows you to early break iterator execution. Also `unwrap` at the end has no relation to `Option` returned in this `scan` - it is because you call `max` on an iterator, and it always returns an `Option` - to have proper value to return in case of empty iterator. If you want to avoid this you may just use single fold: `.fold((0, 0), |(max, prev), x| { let next = prev + x; (std::cmp::max(max, next), next))`.
Could you have used pattern matching or guard instead of if in the Haskell solution rather than if? Still very readable as is.
Apl to Haskell: (a b c)d to map (b a c) d. Or if a is the identity function and b is subtraction and c is 0/1 complement then map ( (-) (1-) ) d
12:20 Readable?! Okay, it might be readable, but I'm sure it's not writable! My keyboard doesn't even have those keys😂
The keyboard layout which you're currently using doesn't have those keys. But you can use an extended keyboard layout: www.microapl.com/apl/introduction_chapter2.html
@@peterye1666 thanks! ☺️
When APL was popular (yes, it was popular), there were dedicated computers with their own keyboards. Today, most people write it in emacs and type out names. For example, typing "rho" converts it to "⍴".
This is also done with Agda, which isn't as terse as APL but also uses non-Latin letters, including math symbols such as "for-each" (∀) and "exists" (∃). Agda is Haskell-based but primarily used for writing mathematical proofs. (The Common Lisp counterpart is ACL2).
Hilarious! This was the question I use to use when interviewing. I interviewed a C++ Dev for a Java opening and he optimized the performance during the interview.
One thing about the Haskell solution, If you do not like the verbose if and are willing to use some language extensions, then with `LambdaCase` you can combine a lambda with an immediate `case` match and write `map (\case '(' -> 1; _ -> -1)`. You could even roll the filter into it with `concatMap (\case '(' -> [1]; ')' -> [-1]; _ -> [])`
I wanted a video like these 7 years ago
how do you code in apl? greek keyboard mappings?
Slick talk, thanks for posting!
If COBOL is self documenting then APL is self encrypting.
I tried my hand with k, and ended up with |/+\-/"()"=\:
I'm honestly surprised how my filter part is much shorter. Does APL lack the each-right/left adverbs?
8:07
The double ends could be avoided in Elixir by writing
Enum.map(fn c -> if c == “(“, do: 1, else: -1 end)
Graphemes is commonly a thing to use when you have unicode characters. Grapheme meaning "A letter of an alphabet". It takes fully written symbols, compared to single characters as `.chars` would do. Where a full symbol is a letter inclusive super/subscripts like umlauts. As it should be ["ë"] , not ["e", "¨"]. Most `.chars` functions would create the wrong 2nd solution. Grapheme is used as a name specifically to emphasize that it is letter based, not character based. You can also see this differentiation in Ruby, as it includes both.
The Ruby solution won't work. You're gonna sum Nil and Integer, which raises "undefined method '+' for Nil class" here:
> inject([]) { |acc, x| acc
Programming languages or Pokemon badges?
what about Go ?
6:48 Doesn't this code totally miss the "nesting" part in "nesting parenthesis"?
Is my following plain old C code functionally equivalent to the Scala example? And yeah, the C function took me less than 3 minutes to write (on my mobile phone, without a code editor), and yeah, it's the throw-away code that I actually would write for a run-once private project, where I'm already sure that all the in-data has correctly nested parentheses (but I'm not a professional programmer, or professional data anything, just an old fashioned computer user that sometimes find it easier, and faster, to write code, than learning to use a complicated app someone else has made). But I wouldn't run somone else, supposedly professional, supposedly generic code, on more realistic data, if I knew it was this horrible.
int horriblySloppyDeepestParenNesting( char str[] )
{ int max=0, current=0;
for( ; *str; str++ )
{ max += ( current > max );
current += ( *str == '(' );
current -= ( *str == ')' );
}
return max;
}
The Scala and APL examples, was the only ones that I think I understood fully, but as far as I can tell, the other ones have the same deficit. How would you write something similar to the following two more robust C functions as a functional programmer?
int deepestParenNesting( char str[] )
/* UTF-8, or fixed 8 bit, encoded and null terminated string.
Return -1 on mismatched parentheses.
*/
{ int max=0, current=0;
for( ; *str; str++ )
if( *str == '(' )
current++;
else if( *str == ')' )
{ if( current max )
max = current;
current--;
}
return ( current == 0 ) ? max : -1;
}
int deepestParenNesting( char str[] )
/* UTF-8, or fixed 8 bit, encoded and null terminated string.
Return negated position in string where first mismatch of parentheses is discovered.
*/
{ int i=0; max=0, current=0;
for( ; str[i]; i++ )
if( str[i] == '(' )
current++;
else if( str[i] == ')' )
{ if( current max )
max = current;
current--;
}
return ( current == 0 ) ? max : -i ;
}
For Elixir, if its terseness you're after, you can do better
```elixir
def max_depth s do
s
|> String.replace(~r/[^()]/, "")
|> String.graphemes()
|> Enum.map(fn "(" -> 1; ")" -> -1 end)
|> Enum.scan(&+/2)
|> Enum.max()
end
```
The function in map uses pattern matching instead of if/else (usually broken down into multiple lines instead of separated by semicolons, but terseness and all that)
The function in scan is the same as what you have, but in a more point-free format. & is the capture operator, and functions in Elixir/Erlang/BEAM are identified with their name and their arity, so that is why we have function + with arity 2 (takes 2 arguments). A bit cryptic to some perhaps, but as OP is a fan of APL, this is straight up plain english in comparison.
Or you can take out the string replace, and add one more condition to the map:
|> Enum.map(fn "(" -> 1; ")" -> -1; _ -> 0 end)
So basically doesn't take out the non-parentheses; it just ignores them in the map.
In Rust you don't need to unwrap because you're getting an array of option. You aren't. It's because max returns an option. The iterator you call max on may be empty so that covers that case.
I am so happy just because of the reason that most of people don't code in APL, world could have been more difficult to understand for developers.
Does anyone recommend any tutorials for getting started with APL?
This a short list of resources:
1. TryAPL.org for a quickstart
2. ruclips.net/user/DyalogConference for free conference videos
3. chat.stackexchange.com/rooms/52405/the-apl-orchard APL Orchard to ask any questions you have
4. dyalog.com for free software download
5. aplwiki.com
As for tutorials, I haven't walked through but I have heard this is good (although a bit old school): tutorial.dyalog.com/
It kinda sound like you didn't know what a grapheme is
What do these look like in Python, Go, Javascript, Java, or C#?
It must look very ugly in those imperative languages
Here's my solution in Factor (concatenative, stack-based language):
USING: kernel arrays math math.order sequences sets ;
IN: Maximum-Nesting-Depth-of-the-Parentheses
: max-depth ( s -- n )
[ "()" in? ] filter >array
[ 2 mod 2 * 1 - neg ] map
0 [ + ] accumulate
swap [ max ] reduce ;
I used simple arithmetics instead of ternary "if" to map () to 1/-1
My JS solution:
Math.max(...input.split("").reduce((c, v) => [...c, c[c.length - 1] += v == "(" ? 1 : v == ")" ? -1 : 0], [0]))
With line breaks it can look like this:
Math.max(
...input
.split("")
.reduce(
(c, v) =>
[
...c,
c[c.length - 1]
+= v == "("
? 1
: v == ")"
? -1
: 0
],
[0]
)
)
I discovered that the "+=" i used in a previous attempt is different from just the addition that would be necessary here. Without the equals, i'd need to wrap the right hand side in parentheses because the addition binds stronger than the equals comparison. This is not the case with plus-equals.