Fibred Sum

Applying Glue to words.

Pulling Apart haskell’s Arrow Types.

Haskell arrows are a strange beast. Most people have a hard time understanding them, and the people that do often see things that are almost arrows but don’t meet 1 of the criteria. For example stream transformers don’t have a valid instance of ***, but they do have an instance for arr, and for +++ and |||. I recently went over them and figured out exactly what each constraint implies.

As Dan Piponi has pointed out, arrows are profunctors. Another way to think about them is that arrows define a category whose objects are haskell types. It’s interesting to ask about what the relations between Hask and this other category are. So here are some possible relations:

Throughout the rest, the non-Hask category will be called C.

  • There is a functor from Hask to C. This is witnessed by arr in the standard arrow package. Note that this is mostly independent from the rest of the relations below, except that if the relations below exist there’s a commuting diagram with arr.
  • The Haskell product is the product in C. Witnessed by &&&.
  • The Haskell product is a monoid in C. Witnessed by ***. This is weaker than above. e. g. Op satisfies this, but not the above. (,) is the sum in Op, but it’s still a monoid
  • The Haskell sum is a sum in C. Witnessed by |||.
  • The Haskell sum is a monoid in C. Witnessed by +++. As above, this is weaker
  • The Haskell product is the product in C, and the type c a b is the exponential in C. This is witnessed by the co-unit of the adjunction: eval. The Haskell arrow package calls this app

I’ve written these out as code below.

*Note that it’s probably possible to be even more general in Haskell and ask whether C has some other product, or some other sum.
and then define the same usfeful functions when it happens to be the Haskell sum and the Haskell product, but I wanted to map out exactly what Arrow was asking for first.

module Category where

import Prelude hiding (fst,snd,(.),id)
import Control.Category

{-
Since the objects of this other category are haskell types describing a functor
between the two is as simple as describing its action on functions. arr does
exactly this
-}
class (Category c) => CategoryFunctor c where
  arr :: (a -> b) -> c a b

class (Category c) => ProductIsMonoid c where
  (***) :: (c a1 b1) -> (c a2 b2) -> (c (a1,a2) (b1,b2))

class (ProductIsMonoid c) => ProductIsCommutatitve c where
  cSwap :: (c (a,b) (b,a))

{-
If defining both instances, *** can be defined in terms of &&& as follows:
 f *** g = (fst >>> f) &&& (snd >>> g)
-}
class (ProductIsMonoid c) => ProductIsProduct c where
  (&&&) :: (c a b1) -> (c a b2) -> (c a (b1, b2))
  fst   :: (c (a,b) a)
  snd   :: (c (a,b) b)

class (Category c) => SumIsMonoid c where
  (+++) :: (c a1 b1) -> (c a2 b2) -> (c (Either a1 a2) (Either b1 b2))

{-
If defining both instances, +++ can be defined in terms of ||| as follows:
 f +++ g = (f >>> left) ||| (g >>> right)
-}
class (SumIsMonoid c) => SumIsSum c where
  (|||) :: (c a1 b) -> (c a2 b) -> c (Either a1 a2) b
  left  :: c a (Either a b)
  right :: c b (Either a b)

class (ProductIsProduct c) => ProductIsClosed c where
  eval :: (c (c a b, a) b)

{-
Here we define instances for (->). (->) Has all the instances, because it is the
same category
-}
instance CategoryFunctor (->) where
  arr = id

instance ProductIsMonoid (->) where
  (***) f g (x,y) = (f x, g y)

instance ProductIsProduct (->) where
  (&&&) f g x = (f x, g x)
  fst (x,y) = x
  snd (x,y) = y

instance ProductIsCommutatitve (->) where
  cSwap (x, y) = (y, x)

instance SumIsMonoid (->) where
  (+++) f g (Left x) = Left $ f x
  (+++) f g (Right x) = Right $ g x

instance SumIsSum (->) where
  (|||) f g (Left x) = f x
  (|||) f g (Right x) = g x
  left = Left
  right = Right

instance ProductIsClosed (->) where
  eval = uncurry ($)

-- Here's a type where we can define some, but not all of the instances.
newtype Op a b = Op (b->a)

instance Category Op where
  id = id
  (Op f) . (Op g) = Op $ g . f

instance ProductIsMonoid Op where
  (Op f) *** (Op g) = Op $ f *** g

instance SumIsMonoid Op where
  (Op f) +++ (Op g) = Op $ f +++ g

Adding DHCPv6-PD support to DD-WRT

I got my new buffalo router this week, and surprisingly, no-one had documented how to do DHCPv6 with Prefix Delegation. I managed to get it working so I thought I would document it so others can find it.

Edit: I added a check to make sure dhcp6c is only running once. My router ended up running multiple copies and having them interfere with each other

Steps:

  1. Set up jffs. You’ll be using it through the rest of these steps
  2. Copy /usr/bin/ipkg /jffs
  3. Edit /jffs/ipkg and change
    IPKG_DIR_PREFIX=/usr/local/lib/ipkg
    to:
    IPKG_DIR_PREFIX=/jffs/usr/local/lib/ipkg
  4. Copy /etc/ipkg.conf /jffs
  5. Edit /jffs/ipkg.conf and add the following source:
    src openwrt-trunk http://downloads.openwrt.org/snapshots/trunk/ar71xx/packages
    comment out the whiterussian source.
  6. jffs update and install needed packges:
    # IPKG_CONF_DIR=/jffs /jffs ipkg update
    # IPKG_CONF_DIR=/jffs /jffs ipkg install wide-dhcpv6-client
    # IPKG_CONF_DIR=/jffs /jffs ipkg install rdisc6
  7. Put the following in /jffs/etc/config/dhcp6c.wanup:
    #!/bin/sh
    if [ ! -f /tmp/var/run/dhcp6c.pid ] ; then
      dhcp6c -c /jffs/etc/dhcp6/dhcp6c.conf -p /tmp/var/run/dhcp6c.pid vlan2
    fi
  8. Put the following in /jffs/etc/config/rdisc6.wanup:
    #!/bin/sh
    echo 2 > /proc/sys/net/ipv6/conf/vlan2/accept_ra
    rdisc6
  9. Make those scripts executable. # chmod 755 /jff/etc/config/*.wanup
  10. Put the following in /jffs/etc/dhcp6/dhcp6c.conf:
    interface vlan2 {
      send rapid-commit;
      send ia-pd 0;
      send ia-na 0;
      request domain-name-servers, domain-name;
      script "/jffs/etc/dhcp6/dhcp6c-script";
    };
    
    id-assoc pd 0 {
      prefix-interface br0 {
        sla-id 0;
        sla-len 0;
      };
    };
    
    id-assoc na 0 {};
  11. Put the following in /jffs/etc/dhcp6/dhcp6c-script:
    #!/bin/sh
    if [ -f /var/run/radvd.pid ] ; then
    	kill -HUP `cat /var/run/radvd.pid`;
    fi
  12. Make dhcp6c-script executable.
  13. Make sure ipv6 is enabled in the web interface, along with radvd. Put the following as radvd.conf:
    interface br0 {
      AdvSendAdvert on;
      prefix ::/64 {};
      RDNSS 2001:558:FEED::1 2001:558:FEED::2 {};
    };
    
  14. Replace the nameservers above if this isn’t for comcast. It’s probably possible with a little work to re-write radvd.conf dynamically based on the received dns servers. This works for now.
  15. Reboot

If you run into an issue following these steps, please contact me. Note that I tried several things first and attempted to distill the results down to instructions. It’s possible that in trying something, I did something relevant that I didn’t record here.