1. 9

  2. 6


    1. 5

      A standard characterization of ADT derivatives might go a bit like

      data Ctx f a = Ctx (Diff f a) a
      class (Functor f, Functor (Diff f)) => Holey f where
        type Diff f :: * -> *
        up :: Ctx f a -> f a
        down :: f a -> f (Ctx f a)
        allAround :: Ctx f a -> Ctx f (Ctx f a)

      If we note that

      type Diff [] a = ([a], [a])

      then the down function is what you’re looking for as it has a type equivalent to

      [a] -> [([a], a, [a])]

      the difference is only that there’s a bit more “location” information preserved by down.

      I’m not sure if there’s a standard characters-in-a-line name for this, but it is a standard notion at least.

      1. 2

        Very interesting. Thanks, especially, for the reference. It does seem that what I have here is a kind of really restricted list element zipper, and that’s probably because the data in question is really more of a set than a list. Order is unimportant to me, and each element is unique. So I went looking to see if there is such a thing as a set element zipper. That turns out to be a bit difficult to Google, and I didn’t come up with much.

        Another commenter on my blog suggested that I’m looking for set partitions. That’s kind of true, but poking around the documentation for partition functions in, say, Mathematica, it seems they’re generally concerned with how many subsets are in the partition or the size of subsets in the partition, but nothing like my “each member and the difference between that member and the original set.” So I like the zipper notion better, since it seems closer to what I’m after.

        1. 4

          There are definitely set zippers! They’re just sets again like you might expect—so if we’re treating lists as sets then you end up exactly with your function.

          ADTs are a bit too weak to display this nicely, but combinatorial species can do it. Take a look at Yorgey’s “Species, Functors, and Types, Oh My!”.

          1. 4

            My understanding was that multisets (as opposed to sets) were their own derivative (which makes sense if you think about their Taylor expansions). Now that I come to think of it, I’m really not sure what the derivative d(Set a)/da looks like …

            1. 1

              Oh, you’re exactly right. I was thinking bags and saying sets.

              1. 2

                Understandable, as the Yorgey paper you cite uses bags when talking about the set species.

            2. 1

              …aaaand now I have two Conor McBride papers on my lap. Wondering how deep this rabbit hole goes…

              1. 1

                Thanks for the reference!

          2. 2

            @craigstuntz post needs tag ‘ask’

            1. 1

              That’s a good idea, and noted for the future, but I can’t find a way to add it.

              1. 2


            2. 2

              By no means standard, but I’d go with (inspired by uncons and nth):

              unnth 0 [1, 2, 3] => [1, [2, 3]]
              unnths [1, 2, 3] => [[1, [2, 3]], [2, [1, 3]] ... ]

              For efficiency reasons, you’d of course do unnths the way you currently do, and not by successive calls to unnth

              1. 1

                I’m not sure that this would be a standard, named function. It’s basically n choose 1 and n choose n-1 zipped together. Relevant Wikipedia: https://en.wikipedia.org/wiki/Combination

                In python:

                [((1,), (1, 2)), ((2,), (1, 3)), ((3,), (2, 3))]
                1. 2

                  This doesn’t get you the same result. In his function, he takes each item out of the list, and returns the [the item, the list without that item]. In Python, you could achieve the same thing like so:

                  def unnth(n, x):
                     xx = x.copy()
                     nn = xx.pop(n)
                     return [nn, xx]
                  def unnths(x):
                     for i in range(len(x)):
                       yield unnth(i, x)
                  >>> list(unnths([1, 2, 3]))
                  [[1, [2, 3]], [2, [1, 3]], [3, [1, 2]]]
                  1. 1

                    Ah, you’re right, my example isn’t correct. I forgot to check the way python orders the combinations before putting them into zip, and one is backwards from what you would want. Doing it this way sort of sucks, though, since you end up with two copies of one of the lists due to how reversed works.

                    [((1,), (2, 3)), ((2,), (1, 3)), ((3,), (1, 2))]
                2. 1

                  How about extractions or removals? Unless I were writing in a context where zippers find further use, I’d call it that:

                  def extractions(xs): 
                      for i, x in enumerate(xs):
                          yield x, xs[:i]+xs[i+1:]