What do we call this (new?) higher-order function?

Question

I am trying to name what I think is a new idea for a higher-order function. To the important part, here is the code in Python and Haskell to demonstrate the concept, which will be explained afterward.

Python:

>>> def pleat(f, l):
       return map(lambda t: f(*t), zip(l, l[1:]))
>>> pleat(operator.add, [0, 1, 2, 3])
[1, 3, 5]

Haskell:

Prelude> let pleatWith f xs = zipWith f xs (drop 1 xs)
Prelude> pleatWith (+) [0,1,2,3]
[1,3,5]

As you may be able to infer, the sequence is being iterated through, utilizing adjacent elements as the parameters for the function you pass it, projecting the results into a new sequence. So, has anyone seen the functionality we've created? Is this familiar at all to those in the functional community? If not, what do we name it?

---- Update ----

Pleat wins!

Prelude> let pleat xs = zip xs (drop 1 xs)
Prelude> pleat [1..4]
[(1,2),(2,3),(3,4)]

Prelude> let pleatWith f xs = zipWith f xs (drop 1 xs)
Prelude> pleatWith (+) [1..4]
[3,5,7]

Answer 1

Here's another implementation for Python which works if l is a generator too

import itertools as it

def apply_pairwise(f, l):
    left, right = it.tee(l)
    next(right)
    return it.starmap(f, it.izip(left, right))

I think apply_pairwise is a better name

Answer 2

Since it's similar to "fold" but doesn't collapse the list into a single value, how about "crease"? If you keep "creasing", you end up "folding" (sort of).

We could go with a cooking metaphor and call it "pinch", like pinching the crust of a pie, though this might suggest a circular zipping, where the last element of the list is paired with the first.

def pinch(f, l):
    return map(lambda t: f(*t), zip(l, l[1:]+l[:1]))

(If you only like one of "crease" or "pinch", please note so as a comment. Should these be separate suggestions?)

Answer 3

So because there seems to be no name for this I suggest 'merger' or simple 'merge' because you are merging adjacent values together.

So merge is already taken so I now suggest 'meld' (or 'merger' still but that may be too close to 'merge')

For example:

meld :: (a -> a -> b) -> [a] -> [b]
meld _ [] = []
meld f xs = zipWith f (init xs) (tail xs)

Which can be used as:

> meld (+) [1..10]
[3,5,7,9,11,13,15,17,19]
> meld compare "hello world"
[GT,LT,EQ,LT,GT,LT,GT,LT,GT,GT]

Where the second example makes no real sense but makes a cool example.

Answer 4

I really can't see any codified names for this anywhere in Python, that's for sure. "Merge" is good but spoken for in a variety of other contexts. "Plow" tends to be unused and supplies a great visual of pushing steadily through a line of soil. Maybe I've just spent too much time gardening.

I also expanded the principle to allow functions that receive any number of parameters.

You might also consider: Pleat. It describes well the way you're taking a list (like a long strand of fabric) and bunching segments of it together.

import operator

def stagger(l, w):
    if len(l)>=w:
        return [tuple(l[0:w])]+stagger(l[1:], w)
    return []

def pleat(f, l, w=2):
    return map(lambda p: f(*p), stagger(l, w))

print pleat(operator.add, range(10))
print pleat(lambda x, y, z: x*y/z, range(3, 13), 3)
print pleat(lambda x: "~%s~"%(x), range(10), 1)
print pleat(lambda a, b, x, y: a+b==x+y, [3, 2, 4, 1, 5, 0, 9, 9, 0], 4)

Answer 5

zipWithTail or adjacentPairs.

Answer 6

I vote for smearWith or smudgeWith because it's like you are smearing/smudging the operation across the list.

Answer 7

BinaryOperate or BinaryMerge

Answer 8

In Python the meld equivalent is in the itertools receipes and called pairwise.

from itertools import starmap, izp, tee

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)

So I would call it:

def pairwith(func, seq):
    return starmap(func, pairwise(seq))

I think this makes sense because when you call it with the identity function, it simply returns pairs.

Answer 9

Hmm... a counterpoint.

(`ap` tail) . zipWith

doesn't deserve a name.

BTW, quicksilver says:

 zip`ap`tail

The Aztec god of consecutive numbers

Answer 10

Using Mathematica

Plus @@@ Partition[{0, 1, 2, 3}, 2, 1] or either of these more verbose alternatives

Apply[Plus, Partition[{0, 1, 2, 3}, 2, 1], {1}]
Map[Apply[Plus, #] &, Partition[{0, 1, 2, 3}, 2, 1]]

I have used and enjoyed this higher order function in many languages but I have enjoyed it the most in Mathematica; it seems succinct and flexible broken down into Partition and Apply with levelspec option.

Answer 11

this seems like ruby's each_cons

ruby-1.9.2-p0 > (1..10).each_cons(2).to_a

=> [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9], [9, 10]] 

Answer 12

This reminds me of convolution from image processing. But not sure if this is mathematically correct.

Answer 13

The generalized variant of the plain zip version of this is what I would think of as window. Not at a ghci terminal right now, but I think window n = take n . tails. Then your function is zipWith (\[x,yj -> f x y) . window 2. This sort of style naturally works better when f is of type [a] -> b.

Answer 14

I'd be tempted to call it contour as I've used it for "contour" processing in music software - at the time I called it twomap or something silly like that.

There are also two specific named 'contours' in music processing one is gross contour - does the pitch go up or down. The other is refined contour where the the contour is either up, down, leap up or leap down, though I can't seem to find a reference for how large the semitone difference has to be to make a leap.

Answer 15

in C++ Standard Template Library, it is called adjacent_difference (though the operator can be any operation, not just subtraction)

Answer 16

Nice idiom! I just needed to use this in Perl to determine the time between sequential events. Here's what I ended up with.

sub pinch(&@) {
  my ( $f, @list ) = @_;
  no strict "refs";

  use vars qw( $a $b );

  my $caller = caller;
  local( *{$caller . "::a"} ) = \my $a;
  local( *{$caller . "::b"} ) = \my $b;

  my @res;
  for ( my $i = 0; $i < @list - 1; ++$i ) {
    $a = $list[$i];
    $b = $list[$i + 1];
    push( @res, $f->() );
  }
  wantarray ? @res : \@res;
}

print join( ",", pinch { $b - $a } qw( 1 2 3 4 5 6 7 ) ), $/;
# ==> 1,1,1,1,1,1

The implementation could probably be prettier if I'd made it dependent on List::Util, but... meh!