undefined | Better HN

0 pointstome5y ago0 comments

> So in the end, as I claimed initially, this function can't be > written in a simple, safe way in Haskell

Steady on! You posed a question and I gave an answer. You weren't happy with that answer. I think it's a bit premature to conclude that "this function can't be written in a simple, safe way in Haskell".

> as the article I linked claims, Haskell's type system can't encode the type of the cl_map function.

Could you say where you see that claim in the article? I can see three mentions of "Haskell" in the body, two of them mentioning that one researcher's particular implementation doesn't handle this case, but not a claim that it can't be done.

> Note that the type of cl_map is perfectly static. It would be `Integer N => (a_0 ->... a_N -> r) -> [a_0] ->... [a_N] -> [r]` assuming some fictitious syntax.

OK, fine, it's a bit clearer now what you are looking for. How about this:

    > cl_map (uncurry (+)) ([1,2,3], [4,5,6])
    [5,7,9]
    > cl_map (+3) [1,2,3]
    [4,5,6]
    > let max3 (x, y, z) = x `max` y `max` z
    > cl_map max3 ([1,2], [3,4], [5,6])
    [5,6]

Notice that the function arguments are have different, statically-known types! The type of this miracle function?

    cl_map :: Default Zipper a b => (b -> r) -> a -> [r]

And the implementation?

    -- Type definition
    newtype Zipper a b = Zipper { unZipper :: a -> ZipList b } deriving Functor

    -- Instance definition
    instance a ~ b => D.Default Zipper [a] b where def = Zipper ZipList

    -- These three instances are in principle derivable
    instance P.Profunctor Zipper where
      dimap f g = Zipper . P.dimap f (fmap g) . unZipper

    instance Applicative (Zipper a) where
      pure = Zipper . pure . pure
      f <*> x = Zipper (liftA2 (<*>) (unZipper f) (unZipper x))

    instance PP.ProductProfunctor Zipper where
      purePP = pure
      (****) = (<*>)

Given that the only two lines that actually matter are

    newtype Zipper a b = Zipper { unZipper :: a -> ZipList b } deriving Functor
    instance a ~ b => D.Default Zipper [a] b where def = Zipper ZipList

and the rest are boiler plate that could be auto-derived, I think this is pretty satisfactory. What do you think?

0 comments

simiones5y ago

First of all, thank you for bearing with me this long!

Still, you haven't written exactly the function I was asking for. You require a manual, compile-time step of transforming the N-ary function to a unary function taking a tuple. Still, it's impressive that this can define variable-length, variable-type tuples. Unfortunately I am not able at all to follow your solution, as it's using too many types that I'm not familiar with, and it seems to require some external packages, so I can't easily try it out in an online compiler to understand it better (as I have been doing so far).

Either way, I would say we are well outside the limits of an easy to understand way of specifying this kind of function - even if you are only showing 2 lines of code, it seems that your definition requires, outside of lists and functions (the objects we intended to work with): ZipList, Default, Functor, Profunctor, ProductProfunctor, Applicative, and a helper type. Even if these were derivable, someone seeking to write this function would still need to be aware of all of these types, some of which are not even part of the standard library; and of the way they work together to magically produce the relatively simple task they had set out to do.

> Could you say where you see that claim in the article?

The claim is presented implicitly: for one, they conjecture that, were Haskell or SML to "pragmatically support" such a feature, it would be used more often (offering as argument the observation that both Haskell's and SML's standard libraries define functions that differ only in the arity of their arguments, such as zipWith/zipWith3 in Haskell). This implies that, to their knowledge, it is not pragmatically possible to implement this in Haskell.

Similarly, given that in their "Related Works" section they don't identify any complete implementation of variadic polymorphism, it can be assumed that they claim at least not to have found one.

tomeOP5y ago

> Still, you haven't written exactly the function I was asking for

I'm afraid I'm now completely stumped about what you're asking for. If you have a function with a known arity and want to apply it to a known number of arguments then you can use the original formulation:

    f <$> args1 <*> args 2 ... <*> argsN

You then asked what happens for unknown numbers of arguments, so I produced a solution that works with lists, which isn't very Haskelly, but does the job. After that you said you wanted something with a more specific type, so I came up with the answer that works generally over tuples (or indeed any type that contains a sequence of arguments). That's not satisfactory either! It seems you literally want a function with type `Integer N => (a_0 ->... a_N -> r) -> [a_0] ->... [a_N] -> [r]`. Well, I don't know how to do that in Haskell -- maybe my most recent solution extends to that -- but nor do I know why you'd want to do that! If you have a known number of arguments the first solution works fine. If you have an unknown number of arguments then you must have them all together in one datastructure, so the most recent solution works fine. Haskellers would be very happy with either of those and I don't see how we're missing out on programming convenience because of that. Maybe you could elaborate?

tomeOP5y ago

> I can't easily try it out in an online compiler to understand it better

Try this. It's a full working program. The packages it depends on are "profunctors" and "product-profunctors".

    {-# LANGUAGE FlexibleInstances     #-}
    {-# LANGUAGE DeriveFunctor         #-}
    {-# LANGUAGE FlexibleContexts      #-}
    {-# LANGUAGE MultiParamTypeClasses #-}
    {-# LANGUAGE TypeFamilies          #-}
    
    module MyExample where
    
    import qualified Data.Profunctor                 as P
    import qualified Data.Profunctor.Product         as PP
    import qualified Data.Profunctor.Product.Default as D
    
    newtype Zipper a b = Zipper { unZipper :: Traverse ZipList a b }
      deriving Functor
    
    instance a ~ b => D.Default Zipper [a] b where
      def = Zipper (P.dimap ZipList id D.def)
    
    instance P.Profunctor Zipper where
      dimap f g = Zipper . P.dimap f g . unZipper
    
    instance Applicative (Zipper a) where
      pure = Zipper . pure
      f <*> x = Zipper ((<*>) (unZipper f) (unZipper x))
    
    instance PP.ProductProfunctor Zipper where
      purePP = pure
      (****) = (<*>)
    
    cl_map :: D.Default Zipper a b => (b -> r) -> a -> [r]
    cl_map f = getZipList . fmap f . runTraverse (unZipper D.def)

j / k navigate · click thread line to collapse

0 pointstome5y ago0 comments

> So in the end, as I claimed initially, this function can't be > written in a simple, safe way in Haskell

> as the article I linked claims, Haskell's type system can't encode the type of the cl_map function.

> Note that the type of cl_map is perfectly static. It would be `Integer N => (a_0 ->... a_N -> r) -> [a_0] ->... [a_N] -> [r]` assuming some fictitious syntax.

OK, fine, it's a bit clearer now what you are looking for. How about this:

    > cl_map (uncurry (+)) ([1,2,3], [4,5,6])
    [5,7,9]
    > cl_map (+3) [1,2,3]
    [4,5,6]
    > let max3 (x, y, z) = x `max` y `max` z
    > cl_map max3 ([1,2], [3,4], [5,6])
    [5,6]

Notice that the function arguments are have different, statically-known types! The type of this miracle function?

    cl_map :: Default Zipper a b => (b -> r) -> a -> [r]

And the implementation?

    -- Type definition
    newtype Zipper a b = Zipper { unZipper :: a -> ZipList b } deriving Functor

    -- Instance definition
    instance a ~ b => D.Default Zipper [a] b where def = Zipper ZipList

    -- These three instances are in principle derivable
    instance P.Profunctor Zipper where
      dimap f g = Zipper . P.dimap f (fmap g) . unZipper

    instance Applicative (Zipper a) where
      pure = Zipper . pure . pure
      f <*> x = Zipper (liftA2 (<*>) (unZipper f) (unZipper x))

    instance PP.ProductProfunctor Zipper where
      purePP = pure
      (****) = (<*>)

Given that the only two lines that actually matter are

    newtype Zipper a b = Zipper { unZipper :: a -> ZipList b } deriving Functor
    instance a ~ b => D.Default Zipper [a] b where def = Zipper ZipList

and the rest are boiler plate that could be auto-derived, I think this is pretty satisfactory. What do you think?

0 comments

simiones5y ago

First of all, thank you for bearing with me this long!

> Could you say where you see that claim in the article?

Similarly, given that in their "Related Works" section they don't identify any complete implementation of variadic polymorphism, it can be assumed that they claim at least not to have found one.

tomeOP5y ago

> Still, you haven't written exactly the function I was asking for

    f <$> args1 <*> args 2 ... <*> argsN

tomeOP5y ago

> I can't easily try it out in an online compiler to understand it better

Try this. It's a full working program. The packages it depends on are "profunctors" and "product-profunctors".

    {-# LANGUAGE FlexibleInstances     #-}
    {-# LANGUAGE DeriveFunctor         #-}
    {-# LANGUAGE FlexibleContexts      #-}
    {-# LANGUAGE MultiParamTypeClasses #-}
    {-# LANGUAGE TypeFamilies          #-}
    
    module MyExample where
    
    import qualified Data.Profunctor                 as P
    import qualified Data.Profunctor.Product         as PP
    import qualified Data.Profunctor.Product.Default as D
    
    newtype Zipper a b = Zipper { unZipper :: Traverse ZipList a b }
      deriving Functor
    
    instance a ~ b => D.Default Zipper [a] b where
      def = Zipper (P.dimap ZipList id D.def)
    
    instance P.Profunctor Zipper where
      dimap f g = Zipper . P.dimap f g . unZipper
    
    instance Applicative (Zipper a) where
      pure = Zipper . pure
      f <*> x = Zipper ((<*>) (unZipper f) (unZipper x))
    
    instance PP.ProductProfunctor Zipper where
      purePP = pure
      (****) = (<*>)
    
    cl_map :: D.Default Zipper a b => (b -> r) -> a -> [r]
    cl_map f = getZipList . fmap f . runTraverse (unZipper D.def)

j / k navigate · click thread line to collapse