Smashing Swift • Hacker News Board

Re: Smashing Swift

#11

Post by JoshTriplett » Sun, Jun 15, 2014, 5:33 PM UTC

The name "Functor" can be confusing; it's a thing you apply a function to, not a function itself.

A Functor is a type t parameterized by some other type a, such that if you have a function from type a to type b, you can apply that function to a t of a and get a t of b.

Most commonly, a functor will be a container of values of type a, and the mapping consists of applying the function to each value, resulting in a container of values of type b.

Other common functors include a computation that returns type a (use composition to apply the function to the result to get a computation that returns type b), or a possibly null pointer to type a (map null to null, map pointer to a to pointer to b).

Re: Smashing Swift

#12

Post by afthonos » Sun, Jun 15, 2014, 5:33 PM UTC

Let's begin with the array. Imagine I have an array of characters:

var a = ['a', 'b', 'c']

I'd like instead to have the index of their position in the alphabet. That's another array of the same length that would look like this:

var i = [0, 1, 2]

To each element in a, there corresponds an element i, at the same index. And the operation we use is the same for each element:

f('a') = 0

f('b') = 1

f('c') = 2

But we could also want an array that gives us the next letter in the alphabet, like so:

var n = ['b', 'c', 'd']

Here the function is:

g('a') = 'b'

g('b') = 'c'

g('c') = 'd'

But we're very much doing the same thing. We call it mapping. So Arrays in Swift have a map function defined that works like this:

var i2 = a.map(f)

We're passing the function to apply to each member, and we get an array back, of the same length, with the result of doing so.

A functor is a generalization of that concept. It takes a type parametrized by another type, say Box and a function from the parametrized type to another type, say f:V -> W. Then, according to rules that are specific to Box, if you map f over Box, you'll get a Box out.

The key is that exactly how a Box becomes a Box is up to Box.

Re: Smashing Swift

#13

Post by orbifold » Sun, Jun 15, 2014, 5:36 PM UTC

More precisely it is an endofunctor in the category whose objects are Swift types and morphisms are functions between Swift types. All this really means is that given a Swift type, say Int or String, there are Arrays of Int or String, and given a function like showInt(a : Int) : String, a functor gives you a function from an Array of Int to an Array of String (in this case it would just apply showInt to each element of the Array and the result would be the Array of String) in such a way that if you have two functions (to keep with the example, say toUppercase(s : String) : String, the function you get by applying the functor to the composition (toUppercase . showInt) is the same as the composition of functions gotten from the application of the functor to the individual functions. In addition it is required that the identity function is mapped to the identity function.

Re: Smashing Swift

#14

Post by tel » Sun, Jun 15, 2014, 5:40 PM UTC

If something is Iterable, it's a Functor, but not the other way around. Iterable implies there's an order to the elements, for instance. It also implies that you could get ahold of the elements if you chose.

Types which are Functors may have orders and may provide access to the elements, but the Functor interface does not provide those means. This allows you to instantitate more restrictive types. For instance (in Haskell notation)

    data Pretend a = Pretend

is a data type with only one element (`Pretend`) that pretends to be a container. Consider the two types

    Array Int
    Pretend Int

You can still consider Pretend to be a Functor (the mapping function is just a no-op) but it certainly isn't iterable.

In Haskell, Iterable is called Foldable and effectively is the following interface

    instance Foldable c where
      toList :: c a -> [a]

but `Foldable` is used because typically instead of converting it to a list you want to fold over the elements

      fold :: Foldable c => (a -> b -> b) -> b -> c a -> b

Re: Smashing Swift

#15

Post by danabramov » Sun, Jun 15, 2014, 5:45 PM UTC

>However, I ran up against the lack of generic protocols myself today (for those with access, there's an interesting debate at https://devforums.apple.com/thread/230611?tstart=0). It seems like a deliberate design choice, but one I'm not really sure about.

So did I! A few more related links if you're interested in this question:

http://schani.wordpress.com/2014/06/11/associated-types-cons...

http://www.artima.com/weblogs/viewpost.jsp?thread=270195 (this is about Scala, but Swift somewhat follows Scala with this design)

https://groups.google.com/forum/#!topic/swift-language/3Ptyd...

Re: Smashing Swift

#16

Post by Dewie » Sun, Jun 15, 2014, 5:57 PM UTC

> Why is that called a functor instead of an iterable or enumerable though?

Probably because 1) it is inspired by category theory rather than some interface/signature from another programming language 2) "Iterable"/"Enumerable" might be misleading.

2): It might make sense for things like arrays, where you can think of the function (fmap) as enumerating/iterating over the array and then, for each value in the array, uses the supplied function on it. But Functors aren't just things that you can iterate over; functions themselves are functors, and function composition is fmap. But how does the iteration-intuition make sense in this case? Other functors are more a kind of "box" than a collection that can be iterated over (for example: the Option/Maybe type). Sure, you can say that you can implement fmap on Maybe by iterating over the data that it holds, namely the single data that it holds, but that doesn't really say much.

Re: Smashing Swift

#17

Post by wting » Sun, Jun 15, 2014, 5:59 PM UTC

A functor is a thing that can be mapped over. For example:

    map abs [-1, 2, 3] => [1, 2, 3]

Arrays are the simplest example, but it looks like an iterable. However functors retain shape whereas iterables don't. For example if we had a tree (represented visually):

    oak = -1
          / \
         2   3

If we used oak as an iterable, we would lose the structure of the tree:

    map abs iter(oak) => [1, 2, 3]

However if tree belongs to the functor typeclass (i.e. implements functor interface), then:

    map abs oak => 1
                  / \
                 2   3

The alternatives to functors are:

1. mutate the existing data structure

2. copy a new one and then mutate (two passes)

3. create a new one while mutating (one pass, increased complexity / bugs)

Re: Smashing Swift

#18

Post by archgrove » Sun, Jun 15, 2014, 5:59 PM UTC

Very interesting, thanks.

I also ran up against another annoying bug/oversight/v0.1ism : You can't inherit from a generic class without becoming generic yourself. So, even if you fully instantiate your parent's type information, you have to be generic as well! For example:

    class Foo { ... }
    class Bar : Foo { ... }

You'd expect Bar to be a non-generic type, but this throws a compiler error. You have to declare:

    class Foo { ... }
    class Bar : Foo { ... }

Which seems just odd. The best workaround I've found thus far is

    class Foo { ... }
    class BarClass : Foo { ... }
    typealias Bar = BarClass

Bleh. I've filed a radar against this one - it seems like an annoying oversight, even for this early version.

Re: Smashing Swift

#19

Post by japhyr » Sun, Jun 15, 2014, 6:05 PM UTC

I have only a passing familiarity with Objective C. Why is one of the "red lines" having no garbage collection?

Re: Smashing Swift

#20

Post by CodeWithCoffee » Sun, Jun 15, 2014, 6:08 PM UTC

Objective-C uses Automatic Reference Counting (Garbage Collection has been deprecated - and ARC works a lot better than the GC implementation), and as Swift had to uses Objective-C's memory model it must also use ARC.