6

The Scala collections api has some pretty interesting properties and I'm wondering how one would implement it in Haskell; or if it's even possible (or a good idea in general). I'm a bit of a haskell newbie so I'd like to hear your thoughts.

The scala map definition looks like this:

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That

An interesting feature of this API is that if you map over a string and your map function returns a character, the result will be of type string (and not a list of characters).

justin
  • 453
  • 1
  • 4
  • 13
  • 3
    In Haskell, a string *is* a list of characters. (This doesn't answer your question in the general case, but I thought it was worth nothing.) – mipadi Jan 13 '11 at 22:03
  • 2
    A good bit of the Scala (2.8) API library resolves around dealing with *existing* types and how to play nicely with them. The two biggest examples are likely `String` and arrays. Without said existing type issues, I believe much of the implicit builders is unneeded (they are designed to allow "collapsing" to a container of the same type as the input). –  Jan 13 '11 at 22:08
  • 3
    pst, not so. See this example from Martin Odersky (http://stackoverflow.com/questions/1722726/is-the-scala-2-8-collections-library-a-case-of-the-longest-suicide-note-in-histo/1728140#1728140) where the issue is that BitSet has a very efficient representation that is only compatible with ints but we would still like to be able to treat it like any Set with map etc. If it was just an "existing types" issue then BitSet could be discarded. – James Iry Jan 13 '11 at 22:35
  • 2
    @James, I was going to say the same thing, but about Maps. `Map(1->2, 3->4).map{ (k,v) => k+v }` results in a Seq, but `Map(1->2, 3->4).map{ (k,v) => (k+1,v+1) }` results in a `Map` because of `CanBuildFrom`. – Ken Bloom Jan 14 '11 at 01:26
  • @James I'm not so sure that's in opposition [I tried to avoid the use of absolute qualifiers] ;-) Thanks for the very good SO link that does show a very nice use-case for even Scala-originating types. –  Jan 14 '11 at 01:39
  • 1
    The implicit CanBuildFrom is, as far as I can tell, a Scala-style type class. In Haskell you could have a multi-parameter type class (I think that might be implementation-dependent,) so you can do the same thing. –  Jan 14 '11 at 09:27

2 Answers2

6

We have something roughly as general as the Scala API. It's called Foldable.

class Foldable t where
  fold :: Monoid m => t m -> m
  foldMap :: Monoid m => (a -> m) -> t a -> m
  foldr :: (a -> b -> b) -> b -> t a -> b
  foldl :: (a -> b -> a) -> a -> t b -> a
  foldr1 :: (a -> a -> a) -> t a -> a
  foldl1 :: (a -> a -> a) -> t a -> a

http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/Data-Foldable.html

sclv
  • 38,665
  • 7
  • 99
  • 204
  • By using `foldMap` the resulting collection (the equivalent of `That` from Scala), depends on which monoid is chosen? Are all collections monoids? – David Powell Jan 14 '11 at 06:09
  • 1
    @Grazer, nearly all collections are monoids. In particular all collections provided by the containers package have Monoid instances. The biggest subset of non-monoid collections that comes to mind are collections that must contain at least one element, because a monoid requires an identity (e.g. empty) collection. – John L Jan 14 '11 at 12:31
2

I want to say this map function in Scala is really closer to this from Haskell:

fmap :: (Functor f) => (a -> b) -> f a -> f b

Where the list type is just another Functor.

dino
  • 1,123
  • 9
  • 13