3

I've got a function that will take a list and return a list of sublists of a specified length:

*Main> neighbors 3 [1,2,3,4]
[[1,2,3],[2,3,4]]

neighbors :: Int -> [a] -> [[a]]
neighbors n xs =
    let ys = take n xs
        zs = drop 1 xs
    in if (length ys < n)
       then []
       else ys : neighbors n zs

While it works, it doesn't look particularly "Haskell-y" to me, so I'm thinking there might be a pattern-match to do the same thing. Is there? Or, perhaps, I'm missing a different, tacit, way of doing this? I've looked at the various split libraries, and https://wiki.haskell.org/Let_vs._Where gave me the tools to get the function working at all.

Josh Wright
  • 58
  • 4
Chris Buck
  • 745
  • 5
  • 15
  • For what it's worth, alternate solutions are [in this twitter thread](https://twitter.com/gabrielg439/status/701460899589017600?lang=en), and in [this related question](https://stackoverflow.com/questions/27726739/implementing-an-efficient-sliding-window-algorithm-in-haskell). – B. Mehta Jul 29 '18 at 16:14

2 Answers2

3

Since the value can be passed at runtime, it would be strange to write the pattern at that moment: the patterns are usually translated into some program logic. Unless you write some sort of interpreter that first generates such pattern, it is not really possible to construct a pattern based on a value.

But we can indeed improve the program, for example:

neighbors :: Int -> [a] -> [[a]]
neighbors n l = go l (drop (n-1) l)
    where go l@(_:lt) (_:xs) = take n l : go lt xs
          go _ _ = []

This works as follows, we define a helper function go, that iterates on the same list, but at two positions: the second list is n-1 positions ahead of the first one. This one "inspects" if there are still enough elements to perform a take. We thus call go with l and drop (n-1) l.

In case the second list is non-empty, we thus know that the "last" item of a take n exists (and that this is n-1 positions ahead). In that case we thus return take n l, and we advance both pointers. From the moment the second list is exhausted, we know that slicing is no longer possible, and hence we stop emitting elements.

The advantage is that this will run on infinite lists, since we never call length on the list (or any other function that needs to run to the end of the list), emitting the next slice itself runs in O(n) due to the take n, but checking if a next slice has to be emitted only takes O(1). If we thus are interested in the k-th element only, it takes O(k+n) time.

Without using explicit recursion, we can use zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] and tails :: [a] -> [[a]]:

neighbors :: Int -> [a] -> [[a]]
neighbors n l = zipWith (const . take n) (tails l) (drop (n-1) l)
Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
  • The length check in my code was on the taken chunk, so there isn't a infinity problem: *Main> take 5 (neighbors 5 [1..]) [[1,2,3,4,5],[2,3,4,5,6],[3,4,5,6,7],[4,5,6,7,8],[5,6,7,8,9]] That being said, I still like the actual solution. – Chris Buck Jul 29 '18 at 17:33
  • 1
    Elegant and efficient. Excellent answer. – dfeuer Jul 29 '18 at 18:21
  • It looks very similar to the one by David Fletcher in the linked duplicate, but the explanation is all different. – dfeuer Jul 29 '18 at 18:42
  • @dfeuer Sure, the "tails" version is very much like the one by David Fletcher, but the first implementation above (without tails) and the explanation, as you suggest, made my day. – Chris Buck Jul 30 '18 at 10:20
2

You can't directly pattern match on the length, but you can post-process it. You're right that your "if length" bit is not very Haskell-y. If I were you, I would just produce all of the tails of at most N elements and then filter off the stragglers at the end.

neighbors :: Int -> [a] -> [[a]]
neighbors n xs = filter (\x -> length x == n) $ go xs
    where go [] = []
          go (y:ys) = take n (y:ys) : go ys

My go here is basically your neighbors without the "if length" bit. Then I filter out all of the elements that are too short. Now, this is better, but we can still do even better. The Data.List module provides tails, which will allow us to eliminate all of our explicit recursion in this case.

import Data.List

neighbors :: Int -> [a] -> [[a]]
neighbors n = filter (\x -> length x == n) . map (take n) . tails

tails returns a list of all of the tails of the given list. Let's go through an example.

-- neighbors 3 [1, 2, 3, 4]
tails                               <==> [[1, 2, 3, 4], [2, 3, 4], [3, 4], [4], []]
map (take n) . tails                <==> [[1, 2, 3]   , [2, 3, 4], [3, 4], [4], []]
filter (...) . map (take n) . tails <==> [[1, 2, 3]   , [2, 3, 4]]

Now we have our problem split into three nice subproblems (produce the tails, take the first N elements, then eliminate the stragglers), and each subproblem is solved by a couple of standard library functions.

Silvio Mayolo
  • 62,821
  • 6
  • 74
  • 116