5 ms·

I could imagine the above being expressed very concisely and elegantly in a language like Haskell: f = sum $ map (\x -> if x == 'a' then 2 else 0) I tend

by aduffy 10y ago

I could imagine the above being expressed very concisely and elegantly in a language like Haskell: f = sum $ map (\x -> if x == 'a' then 2 else 0) I tend to think that as the accumulation condition gets more complicated, the for loop begins to be the clearer choice, but of course there's always a way to simplify into a number of map steps. This can lead to a bunch of allocation overhead for the intermediate lists unless iterators are used in languages where those are supported. EDIT: Whoops, read and replied on mobile, missed the parseLine() call :/ EDIT EDIT: Looks like my code matched the parent as of when I read it, before the edit. wyager is correct that I messed up my point-free syntax

lgas 10y ago
Your function doesn't do the same thing his does -- his skips comparing some of the lines because he's selectively incrementing the loop counter.
- aduffy 10y ago
  I wrote the comment before the parent made their edit so the logic did match what it was at the time. Having said that it would've been a very simple extension to make it a recursive algorithm which includes the else case, and arguably would be clearer than the for loop solution.
- sgk284 10y ago
  I think that's a perfect example of why a functional implementation is superior here. The index is being mutated in two different spots (i++ and i += 2) and it's easy to miss the fact that the i += 2 isn't just a running sum but actually impacting the future traversal. In Haskell you'd do something like: skip [] = [] skip ("a":xs) = skip (drop 2 xs) skip (x:xs) = x : (skip xs) Which makes it super clear that you're skipping over items in the list. The parsing then simply becomes: map parseLine (skip lines) Which is at least an order of magnitude clearer and doesn't mix a bunch of unrelated logic together. Even worse, the original author says the goal of his code is to: > The goal is to skip the line after a line starting with the letter "a". But he actually skips two lines after an "a". The above Haskell code makes it clear that we're skipping two lines with "drop 2".
  - junke 10y ago
    Note that you are using lists, not arrays. Lists admit a simple recursive definition at the type level, which helps writing recursive code. But if you had to use arrays, how would you do?
    - Peaker 10y ago
      import Control.Lens.Cons case uncons v of Nothing -> .. empty vector .. Just (head, tail) -> ..
      - junke 10y ago
        Interesting, thanks. I am right that this will extract consecutive views of the original array as pairs of (item, slice) elements? I guess array elements need not be copied, but there will still be a slight memory overhead, right? or is it some "zero-cost" abstraction? I am not trying to attack the code for efficiency, just curious about what current implementations can make from this.
        Peaker 10y ago
        It shouldn't copy anything - I'd expect it to be optimized to not allocate any memory at all.
    - sgk284 10y ago
      The main takeaway from my example, I'd hope, wouldn't be that recursion is awesome (though it is). It's really trying to highlight that separation of concerns, purity, and building functionality through composition of smaller pieces can lead to beautiful and simple code. And while this is possible in an imperative style, the functional style tends to encourage this behavior more consistently. Using lists and recursion just further lends itself to this style. In op's example, he's simultaneously tracking loop state, figuring out which lines to parse, and parsing those lines. It's a very imperative way to do it. I'd prefer to look at the problem through another lens: Q1: What is he doing? A1: Parsing a subset of lines. Q2: How do you determine the subset of lines? A2: Skip lines that are equal to "a" and two lines after that. That's what led to the two sections of my code. Concerns have been separated. If I was forced to use arrays and, furthermore, work in an imperative language, I'd still have one function to parse the lines and one function to figure out which lines to parse. In Python, first compute which indices are of interest: def indices(xs): i = 0 while i < len(xs): if xs[i] == "a": i += 3 else: yield i i += 1 And have a separate place for actually parsing each line: [parseLine(lines[i]) for i in indices(lines)] This translates relatively nicely to Haskell as well, though definitely feels a little forced / unnatural: indices lines = indices' 0 where indices' i | i >= (length lines) = [] | shouldSkip = indices' (i + 3) | otherwise = i : (indices' (i + 1)) where shouldSkip = (lookup i lines) == Just "a" [parseLine <$> (lookup i lines) | i <- (indices lines)]
- spraak 10y ago
  His? Could be hers..
  - spraak 10y ago
    I wonder why I would be downvoted for pointing this out? The gender is assumed here, when we don't know. Why is this wrong to point out? I don't see anywhere in a Hacker News profile where one can indicate one's gender, so we can't assume what it would be.
    - dvfjsdhgfv 10y ago
      Well, because of recent cultural changes you have several options here, but none are elegant/natural. You can put "he or she" everywhere, or use "they" instead, even though you mean a single person. Many modern writers explicitly use "her" consistently whenever a gender-neutral singular pronoun is needed. I upvoted you, but I perfectly understand why others would react differently - in today's world you can hardly do anything without touching politics, and we're just fed up with that.
      - spraak 10y ago
        > in today's world you can hardly do anything without touching politics, and we're just fed up with that. This makes sense, and I appreciate your reply. I don't think however that it's anything new (or specific to this time period), and even being born means you will constantly be challenged to learn new things, or stay stuck. Also I am not sure about the 'political' sense of this.. I mean, people of different gender identities and beliefs have formed political groups, but I don't think it's a direct connexion. (I do prefer 'they')
      - jjnoakes 10y ago
        > or use "they" instead, even though you mean a single person Using 'they' to mean a single person is valid though. https://en.oxforddictionaries.com/definition/they https://en.oxforddictionaries.com/definition/they
  - lgas 10y ago
wyager 10y ago
I think you want to replace the "$" with a ".". But either way, you haven't done the same thing as the GP. It's not actually clear what the GP's algorithm is supposed to do, and I made the same reading mistake at first as well. > I tend to think that as the accumulation condition gets more complicated, the for loop begins to be the clearer choice You can just use recursion. It's very easy to translate a loop into a tight tail-recursive function in Haskell. The generated assembly code usually looks about the same. In the most extreme case, you can just do a loop inside the State monad, which allows you to get (better defined) imperative semantics without mutability (although the compiler will often generate mutable-equivalent assembly when it sees that doing so is safe). > This can lead to a bunch of allocation overhead for the intermediate lists Haskell uses list fusion so this usually isn't a concern. I transliterated the OP's example in another comment. It's a pretty straightforward recursive function of type e.g. "Int -> ByteString -> Int". Substitute ByteString with whatever constant-lookup data structure you want.
- aduffy 10y ago
  With Haskell this isn't an issue because lists are evaluated lazily, but what I was trying to get at and failed to make clear was that other languages which allow functional-like behavior can result in unnecessary allocation. For example in Python doing multiple maps/filters will allocate multiple lists unless you use the itertools versions in Python 2.7.
  - sgk284 10y ago
    I think the proper answer here is that Python 2.x should be treated as legacy. Python 3.x defaults to generators for maps/filters by default.
  - wyager 10y ago
    > With Haskell this isn't an issue because lists are evaluated lazily Even more than that, the compiler will actually do things like replace map f . map g with map (f . g) To eliminate unnecessary allocations.
    - 10y ago

by aduffy 10y ago

lgas 10y ago

Your function doesn't do the same thing his does -- his skips comparing some of the lines because he's selectively incrementing the loop counter.

aduffy 10y ago
I wrote the comment before the parent made their edit so the logic did match what it was at the time. Having said that it would've been a very simple extension to make it a recursive algorithm which includes the else case, and arguably would be clearer than the for loop solution.
sgk284 10y ago
I think that's a perfect example of why a functional implementation is superior here. The index is being mutated in two different spots (i++ and i += 2) and it's easy to miss the fact that the i += 2 isn't just a running sum but actually impacting the future traversal. In Haskell you'd do something like: skip [] = [] skip ("a":xs) = skip (drop 2 xs) skip (x:xs) = x : (skip xs) Which makes it super clear that you're skipping over items in the list. The parsing then simply becomes: map parseLine (skip lines) Which is at least an order of magnitude clearer and doesn't mix a bunch of unrelated logic together. Even worse, the original author says the goal of his code is to: > The goal is to skip the line after a line starting with the letter "a". But he actually skips two lines after an "a". The above Haskell code makes it clear that we're skipping two lines with "drop 2".
- junke 10y ago
  Note that you are using lists, not arrays. Lists admit a simple recursive definition at the type level, which helps writing recursive code. But if you had to use arrays, how would you do?
  - Peaker 10y ago
    import Control.Lens.Cons case uncons v of Nothing -> .. empty vector .. Just (head, tail) -> ..
    - junke 10y ago
      Interesting, thanks. I am right that this will extract consecutive views of the original array as pairs of (item, slice) elements? I guess array elements need not be copied, but there will still be a slight memory overhead, right? or is it some "zero-cost" abstraction? I am not trying to attack the code for efficiency, just curious about what current implementations can make from this.
      - Peaker 10y ago
        It shouldn't copy anything - I'd expect it to be optimized to not allocate any memory at all.
  - sgk284 10y ago
    The main takeaway from my example, I'd hope, wouldn't be that recursion is awesome (though it is). It's really trying to highlight that separation of concerns, purity, and building functionality through composition of smaller pieces can lead to beautiful and simple code. And while this is possible in an imperative style, the functional style tends to encourage this behavior more consistently. Using lists and recursion just further lends itself to this style. In op's example, he's simultaneously tracking loop state, figuring out which lines to parse, and parsing those lines. It's a very imperative way to do it. I'd prefer to look at the problem through another lens: Q1: What is he doing? A1: Parsing a subset of lines. Q2: How do you determine the subset of lines? A2: Skip lines that are equal to "a" and two lines after that. That's what led to the two sections of my code. Concerns have been separated. If I was forced to use arrays and, furthermore, work in an imperative language, I'd still have one function to parse the lines and one function to figure out which lines to parse. In Python, first compute which indices are of interest: def indices(xs): i = 0 while i < len(xs): if xs[i] == "a": i += 3 else: yield i i += 1 And have a separate place for actually parsing each line: [parseLine(lines[i]) for i in indices(lines)] This translates relatively nicely to Haskell as well, though definitely feels a little forced / unnatural: indices lines = indices' 0 where indices' i | i >= (length lines) = [] | shouldSkip = indices' (i + 3) | otherwise = i : (indices' (i + 1)) where shouldSkip = (lookup i lines) == Just "a" [parseLine <$> (lookup i lines) | i <- (indices lines)]
spraak 10y ago
His? Could be hers..
- spraak 10y ago
  I wonder why I would be downvoted for pointing this out? The gender is assumed here, when we don't know. Why is this wrong to point out? I don't see anywhere in a Hacker News profile where one can indicate one's gender, so we can't assume what it would be.
  - dvfjsdhgfv 10y ago
    Well, because of recent cultural changes you have several options here, but none are elegant/natural. You can put "he or she" everywhere, or use "they" instead, even though you mean a single person. Many modern writers explicitly use "her" consistently whenever a gender-neutral singular pronoun is needed. I upvoted you, but I perfectly understand why others would react differently - in today's world you can hardly do anything without touching politics, and we're just fed up with that.
    - spraak 10y ago
      > in today's world you can hardly do anything without touching politics, and we're just fed up with that. This makes sense, and I appreciate your reply. I don't think however that it's anything new (or specific to this time period), and even being born means you will constantly be challenged to learn new things, or stay stuck. Also I am not sure about the 'political' sense of this.. I mean, people of different gender identities and beliefs have formed political groups, but I don't think it's a direct connexion. (I do prefer 'they')
    - jjnoakes 10y ago
      > or use "they" instead, even though you mean a single person Using 'they' to mean a single person is valid though. https://en.oxforddictionaries.com/definition/they https://en.oxforddictionaries.com/definition/they
- lgas 10y ago

wyager 10y ago

I think you want to replace the "$" with a ".". But either way, you haven't done the same thing as the GP. It's not actually clear what the GP's algorithm is supposed to do, and I made the same reading mistake at first as well. > I tend to think that as the accumulation condition gets more complicated, the for loop begins to be the clearer choice You can just use recursion. It's very easy to translate a loop into a tight tail-recursive function in Haskell. The generated assembly code usually looks about the same. In the most extreme case, you can just do a loop inside the State monad, which allows you to get (better defined) imperative semantics without mutability (although the compiler will often generate mutable-equivalent assembly when it sees that doing so is safe). > This can lead to a bunch of allocation overhead for the intermediate lists Haskell uses list fusion so this usually isn't a concern. I transliterated the OP's example in another comment. It's a pretty straightforward recursive function of type e.g. "Int -> ByteString -> Int". Substitute ByteString with whatever constant-lookup data structure you want.

aduffy 10y ago
With Haskell this isn't an issue because lists are evaluated lazily, but what I was trying to get at and failed to make clear was that other languages which allow functional-like behavior can result in unnecessary allocation. For example in Python doing multiple maps/filters will allocate multiple lists unless you use the itertools versions in Python 2.7.
- sgk284 10y ago
  I think the proper answer here is that Python 2.x should be treated as legacy. Python 3.x defaults to generators for maps/filters by default.
- wyager 10y ago
  > With Haskell this isn't an issue because lists are evaluated lazily Even more than that, the compiler will actually do things like replace map f . map g with map (f . g) To eliminate unnecessary allocations.
  - 10y ago