Strict Partitions

Place to put summaries and problem solutions (probably wrong). An attempt to track/incentivize regular learning.CS?Math?Engineering?(Poetry???)

[shockexpansion]

Bifunctors (simple)

newtype BiComp bf fu gu a b = BiComp (bf (fu a) (gu b))

try applying BiComp to Either,Const(),Identity,a, andb, in this order.

BiComp Either const () Id a b = BiComp (Either (const () a) (Id b)) which simplifies to Left () and Right b which is isomorphic to Nothing and Just b the two parts of Maybe! Since Functors are closed under composition and addition, its nice to see that Maybe is a Functor that we can build up out of basic parts (and such is the case for more complex ones too)

[shockexpansion]

Strict Partitions

OEIS A000009 - gross generator function.

I was looking at potentially a way to speed up a problem solver I wrote and so was looking into this problem. “Given some natural number n how many ways are there to sum up to it without repeating digits”. For example, 4 can be summed as [1,3],[4] and so the number is 2. Turns out, knowing this number isn’t particularly useful for me, since it grows so quickly and also you would need to know what the numbers are specifically to prune anything out (for example, we would want to prune 2 out from our 4 example earlier since it can’t sum up but its probably too computationally expensive to find it and do so, it depends on if you have to brute force it).  Alternatively I was considering only trying a certain number of options, but again you need to know the numbers so it depends on if generating the actual partitions is efficient.

Although it did lead me to a code golf question, and as much as I can’t golf for the life of me, it reminded me of why I like Haskell so much and its because its the most efficient yet readable/understandable of all.

Consider sum [1 | x = subsequence(1..n), sum x == n] which I find brilliant since you sum the list of 1's the comprehension generates, and finding the sum of the subsequences is done more efficiently probably than I could figure out but is still pretty simple and elegant. The filter is also great, simply setting the condition of the sum equalling n.

[shockexpansion]

Functors

I keep confusing myself with these, and references to List and Maybe as Functors is also confusing so I want to clear this up for myself (and provide a reference for myself in the future in case I forget).

Its not untrue that they’re Functors but they are also Not Functors sort of. They’re more like domains that can be lifted to by Functors if that makes more sense? But since there isn’t a name for these Functors, we call it a List Functor or a Maybe Functor I suppose.

So the Functor Law (from the Haskell Wiki - a Quite Reliable Source) says that Functors must follow two Laws. Identity preservations (fairly trivial), and composition which is a little more complicated. I think Id is fairly trivial so I’m going to ignore Id.

First things first, basics. fmap is defined as fmap :: (a -> b) -> f a -> f b. The f is referring to the (a -> b)

So when we talk about List or Maybe being functors what we mean is that we can take some Function f defined as f :: a -> b and then call fmap f (Maybe a) and we will get Maybe b out of it, which means that we can do a -> b without taking it out of the Maybe “wrapper”. In a purely category theory sense, a functor is the transformation the normal types a and b to the wrapped types Maybe a and Maybe b and since its a functor the morphism (function) is also preserved into the Maybe domain, it turns into a Maybe a -> Maybe b.

Now, lets talk about composition (Id is simple, Id should be the same in all domains, if its a -> a then it certainly should be Maybe a -> Maybe b). Composition says composition of morphisms is preserved so

fmap (f . g)  ==  fmap f . fmap g

I think this is most easy to do by example. Lets even use List as an example so that we can see how functions can effortlessly lift. Composition rule says that if   f :: a -> b and g :: b -> c and you fmap f . g which is the same as fmap g ( f a) you will get the same as if you did the two fmaps separately. That means that   fmap f . fmap g is the same as fmap g (fmap f a). Ok. Confusing. Lets make a list, lst = [1..26] and lets have some f map integers to letters f :: Int -> Char. Obviously if we fmap f lst we will get a list of of letters back (A-Z if we implement f right) but lets say we also implement g :: Char -> String where each character became a word starting with that letter. So there are two different ways of doing it right? fmap f . g  will compose f and g together, which means that it goes Int -> Char -> String which becomes Int -> String and then that function is mapped over the list. Alternatively, we can do fmap f . fmap g - first we want to fmap f lst which gives us a list of Chars and then we map over g mapping Strings from the Chars in the list.