18 ms·
I disagree with the premise of this article. Sometimes using a mutable variable really is the simplest way to implement something: def min(foo: List[int]) ->
by ch33zer 6y ago
I disagree with the premise of this article. Sometimes using a mutable variable really is the simplest way to implement something:
def min(foo: List[int]) -> Optional[int]:
min = None
for val in foo:
if min is None or val < min:
min = val
return min
I argue this is much easier to read than the recursive version without assignments:
def min(foo: List[int]) -> Optional[int]:
if not foo:
return None
else if len(foo) == 1:
return foo[0]
else:
rest_min = min(foo[1:])
return rest_min if rest_min < foo[0] else foo[0]
We're optimizing for readability, and sometimes readability means mutable variables. This is to says nothing about performance which is often much better with mutable variables in languages like C++.
Edit: people have posted better version of my code in the comments. Take a look for more pythonic examples.
- samhh 6y agoFirstly, there's a nuance here that readability is heavily dependent upon the language. A language where recursion is the recommended approach to these sorts of problems will have far better syntax for doing so, such as in Haskell. Secondly, I think there's something to be said for familiarity. I think looping is second nature to most of us not because it's superior or more intuitive, but because traditionally this is one of the first things we're all taught. If functional programming were the norm and people were taught recursion early on instead I think your notion of simplicity would differ. I've been teaching a little bit of programming to a beginner lately, and they've often found functional approaches to problems easier to grasp than their imperative equivalents because they're more mathematical. It's like an expression of something they already know versus looping, mutability, et al which are new concepts entirely.
- Scarbutt 6y agoAs someone who learnt to program in Scheme, this was true for me, did so much Scheme that when doing some C or JS I had to pause for moment and think harder when writing imperative loops.
- seanmcdirmid 6y agoLooping has a huge advantage in terms of how we do things in real life. We don’t think of “pound 100 fence posts into the ground” recursively. Recursion is much more of a mathematical concept that we learn about long after preschool, while my 3 year old already gets loops.
- jacksnipe 6y agoHonestly I'm going to disagree. Yes, when planning the task, I think about it as "I have to do this 100 times". But when I'm actually performing the task, I think "Ok, I have to get this stake in the ground, then proceed w/ the rest of my giant pile of stakes." On the flipside, I have a lot of mathematical training, so maybe this is an uncommon perspective.
- deleted 6y ago[deleted]
- loup-vaillant 6y ago> Looping has a huge advantage in terms of how we do things in real life. Anthropomorphism is the bane of our craft. Our untrained intuitions don't really matter. > Recursion is much more of a mathematical concept that we learn about long after preschool Programming is applied mathematics. Different from the kind of maths you learn at school of course, and often even more rigorous. I personally have no qualms about requiring some mathematical proficiency in programming. Makes you much more capable at a number of applications later on.
- jmilloy 6y ago> Our untrained intuitions don't really matter. On the contrary, we have no choice but to use our intutions, at whatever level of training they are at, all the time. So it matters a lot. If A is easier than B iff we learn to think differently, but learning to think differently is harder than just doing B, then A isn't actually easier than B.
- 6y ago
- andrewprock 6y agoRecursion tends to strip context. That is one of the features, and one of the drawbacks. All problems are either a base case, or the general case. If you are attempting to debug logic, it often helps to have all the context. To do that in recursion, you have to travel up and down the stack, examining local contexts one by one.
- jbjohns 6y agoI'm not sure what you mean here. The only thing I can come up with is you're talking about writing specific code recursively but when doing functional programming we usually just use the applicable recursive function (e.g. map, filter, reduce) in which case we have better context than with a loop because a loop has a lot of irrelevant implementation details cluttering up the context.
- baddox 6y agoIt's also probably the case that readability is not a primary concern when implementing things like "min" that will most likely be in the standard library of a programming language. From my limited experience looking at such source code, there tend to be a surprisingly large about of code for fixing edge cases, esoteric performance problems, etc. It may be instructive to look at how readable a very naive implementation of a basic function like "min" is, but it probably doesn't actually matter that much in practice, because you'll be using what the standard library offers (and its implementation is probably much less straightforward than you might think).
- edflsafoiewq 6y agoI agree with you, but your second function differs from your first too much to be a good comparison. This would be closer def min(foo: List[int], default=None) -> Optional[int]: if not foo: return default cur_min = foo[0] if default is None or foo[0] < default else default return min(foo[1:], cur_min)
- michaelhoffman 6y ago#!/usr/bin/env python3 from functools import reduce from typing import List, Optional def min_pair(min: Optional[int], val: Optional[int]) -> Optional[int]: if min is None or val < min: return val else return min def min(foo: List[int]) -> Optional[int]: return reduce(min_pair, foo)
- deleted 6y ago[deleted]
- loup-vaillant 6y agoI have changed my views since. I'm now much more okay with mutation than I used to be, under certain conditions. Ideally I want my mutations to stay local (at the function or module/class scope), and have as few cross module consequences as possible. My view of a program is that of a dependence graph, ideally directed acyclic. Ideally we want that graph to be as sparse as possible: good old decoupling. Mutable state (not just global variables) tend to introduce hidden dependencies, making that graph denser than what it initially appears. That can be a killer. Surprisingly though, as years pass, I am less and less certain what the "correct" structure of a program should be. I sure want to keep it small, simple, easy to maintain… but the method to achieve this still eludes me.
- mannykannot 6y agoIn general I share your increasing uncertainty, but I think it is safe to say that understanding a program is made much more difficult once one has the possibility that a variable might be modified outside of the scope it is created for. The idiom of using mutable variables to track the current state of affairs in a loop is harmless up to the point where one or more is passed by mutable reference to a subroutine or impure function; at that point, it has, almost literally, fallen down a rabbit-hole wherein almost anything could happen.
- chubot 6y agoYeah exactly, I think of this as "imperative in the small" and "functional in the large". There's no real cost to local state, but there's a big cost to tracking global state. (Although game programmers seem to have necessarily built their mental models on global state, and think about it differently. Their programs generally don't get maintained for decades though.) But "functional in the large" is basically the same thing as dependency injection in OOP languages. State and I/O are explicit parameters rather than globals. Here is a comment I wrote about that a long time ago, on Disadvantages of Purely Functional Programming: https://news.ycombinator.com/item?id=11841893 https://news.ycombinator.com/item?id=11841893 To me there's no real advantage to expressing something like "split a string by a delimiter" in a purely functional style. Either way, you have a trivial referentially transparent function you can reuse without causing complexity in your program. You might as well do the obvious imperative thing. ... So both "functions and data" are effectively and usefully implemented as classes. The key is to make some classes like functions, and some classes like data. And have more of a bipartite dependency graph, where functions depend on data, and data depends on functions. ----- I also explicitly structure the program as a graph, which I try to make acyclic, but again the problems and solutions are domain-specific. (Programming is very diverse and programmers tend to generalize from their own few examples.) For example, Compilers and interpreters are inherently mutually recursive, which gives you cyclic dependencies. As far as I can tell, this is the essential reason that Fabrice Bellard's QuickJS has one file that's 70K lines of C. And you can see the same thing if you look at the Zig compiler. In Oil I "modularize" the cyclic dependencies so you can plug them in and out at runtime (which is actually used in the program), but it has a performance cost.
- rapind 6y agoI actually prefer to latter. The guards are very clear and self documenting.
- andrepd 6y agoTo have an honest comparison, don't compare imperative code in an imperative language with functional code in an imperative language. Compare with functional code in a functional language, e.g. ocaml: let list_min l = reduce min l I find this crushingly simple to write and to reason about, much more than the convoluted and inefficient imperative code. EDIT: for completeness, here's the definition of `reduce` and `min`: let reduce op l = match l with | [] -> invalid_arg "reduce: empty list" | [x] -> x | hd::tl -> op (hd) (reduce op tl) let min a b = if a < b then a else b
- athenot 6y agoWhile I agree with the sentiment with comparing apples to apples, I happened to notice this can be expressed nearly as elegantly in CoffeeScript: list_min = (l) -> reduce min, l With the definitions being: min = (a, b) -> if a < b then a else b reduce = (op, l) => switch when l.length is 0 then throw "reduce: empty list" when l.length is 1 then l[0] else reduce op, [(op l[0], l[1]), l[2..]].flat()
- rovolo 6y agoHere's how it would look in python: from functools import reduce def min2(a, b): if a < b: return a return b def min(list): return reduce(min2, list, None)
- saagarjha 6y ago> from functools import reduce Oh, Python…
- scrollaway 6y agoreduce() used to be in the builtins in python 2.x. It was removed due to low usage. Keeping the builtins list tiny is a core principle of the language.
- 6y ago
- deleted 6y ago[deleted]
- howling 6y agoI would have written two functions instead where one takes a default argument and the other returns None if the list is empty. In pseudo-Haskell notation: min1 : Int -> List Int -> Int min1 def Nil = def min1 def (Cons x xs) = min1 (def if def <= x else x) xs min : List Int -> Maybe Int min Nil = None min (Cons x xs) = min1 x xs
- gentleman11 6y agoFrom what I’ve read, the goal isn’t always simplicity of reaing/writing code, but the simplicity of implementing multi threading
- bobbylarrybobby 6y agoIt doesn't bother you that you're checking `min is None` even after you know it can't be (i.e., after one loop iteration)? Python doesn't make it pretty to get around this issue: def min(foo): it = iter(foo) try: m = next(it) except StopIteration: return None for val in it: if val < m: m = val return m
- zanderwohl 6y agoYou could switch the order they're compared and due to short-circuiting the second eval would only ever take place once. Or initialize min to the zeroth item in the array.
- wyager 6y agoThis is a great example of how people who use ad-hoc languages can get distorted views of how recursion should be denoted. No functional programmer in the universe would write something that looks like your recursive example. Here are two recursive ways to write a min function: Idiomatic and structured, using (Maybe . Min) monoid: min = foldMap (Just . Min) Incidentally, the above works on any data structure where this operation makes sense, not just lists, which is nice. Unstructured, ad-hoc minimum [] = Nothing minimum (x:xs) = case minimum xs of Nothing -> Just x; Just y -> Just (min x y) This latter doesn’t even rely on anything unique to functional programming ecosystems (like folds or principled algebraic classes).
- virtualwhys 6y agoDepends on the language. In Scala the idiomatic approach would be to favor the immutable/recursive version. def min(foos: List[Int]): Option[Int] = foos match { case Nil => None case x :: Nil => Some(x) case x :: xs => min(xs).filter(_ < x) orElse Some(x) }