Skip to content

Instantly share code, notes, and snippets.

@dmitriz
Last active May 28, 2019 04:04
Show Gist options
  • Save dmitriz/4d5f0ffcad33a75f3a534df3a330eb30 to your computer and use it in GitHub Desktop.
Save dmitriz/4d5f0ffcad33a75f3a534df3a330eb30 to your computer and use it in GitHub Desktop.
Array functor uglified

Let us make the array functor slightly uglier.

According to Functor's definition, for every type a, we first need to define the type F(a), the set of all admissible values for our Functor.

For the array Functor Array, that would be the set [a] of all arrays with entries of type a.

We now define a new Functor F, where we slightly change the set of values F(a): Namely, we say that an array arr is of type F(a) if either

(1) arr.length !== 1

or

(2) arr === [0]

In other words, any array is allowed apart from length 1, where only the array [0] is allowed.

Now define the map:

// (a -> b) -> F(a) -> F(b)
const map = f => arr => 
    (arr.length === 1) ? [0] : arr.map(f)

I think this provides a Functor, because all the functor laws can be checked independently for arrays of a fixed lengh.

@i-am-tom
Copy link

The type definition of such an array would have to be

data ModifiedList a = Nil | SingleZeroList | Cons a (Array a)

So it's a list with a fixed special case. I think, in terms of encoding, this is actually just an obfuscated Maybe List - the list itself is still unbreakable, hah :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment