4 ms·

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 us

by 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)]
- junke 10y ago
  > This translates relatively nicely to Haskell as well, though definitely feels a little forced / unnatural: Thanks for the answer. I must say that I find the original problem quite artificial.

by 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)]

junke 10y ago
> This translates relatively nicely to Haskell as well, though definitely feels a little forced / unnatural: Thanks for the answer. I must say that I find the original problem quite artificial.