4

I'm working on Problem 19 in Ninety-Nine Haskell Problems, and I've encountered the following difficulty. The problem asks to "rotate a list N places to the left." This could easily be achieved in a pointed way, e.g.,

rotate :: [a] -> Int -> [a]
rotate xs n = drop n xs ++ take n xs

However, for my own edification and for the challenge, I'd like to implement this in a point-free way using applicative functors. For instance, one can eliminate one of the arguments by using the fact that (->) [a] is an Applicative functor and implement rotate as follows:

rotate :: Int -> [a] -> [a]
rotate n = (++) <$> drop n <*> take n

Ideally, one should be able to eliminate both arguments, and write it as

rotate :: [a] -> Int -> [a]
rotate :: (++) <$> drop <*> take

but this causes a type error. (I'm not sure exactly how the type are being inferred, but the problem seems to be coming from the fact that the inferred Applicative functor is (->) Int rather than (->) ((->) Int [a]).)

One way to solve this would be to manually implement (->) ((->) a b) as an instance of Applicative, and, in particular, set

<*> f g x y = f x y (g x y)

but it seems that there should be a cleaner way to do this inline. What is the "right" way to solve this problem?

6
  • For what its worth, pointfree.io give rotate = ap ((<*>) . ((++) <$>) . drop) take.
    – chepner
    Commented Aug 20, 2019 at 17:48
  • You can always ask pointfree to do it for you. It uses ap instead of <*> but it's the same thing. Commented Aug 20, 2019 at 17:50
  • 6
    Maybe I'm missing something, but it seems to me that (->) (-> a) b is not even a valid type, because (->) expects first type argument of kind *, but (-> a) :: * -> * Commented Aug 20, 2019 at 18:06
  • Sorry, you're absolutely right. It should have been (->) a (-> b). Thanks for the correction.
    – jgaeb
    Commented Aug 20, 2019 at 20:36
  • 4
    @jgaeb (->) a (-> b) is also invalid (ill-kinded) since the second argument of (->) must have kind * but (-> b) has kind * -> *.
    – chi
    Commented Aug 20, 2019 at 21:12

2 Answers 2

14

There's an "optimal" way of doing this without using the Applicative instance.

import Data.Semigroup
rotate = drop <> take

We can be explicit about the type (<>) is instantiated at

{-# Language ScopedTypeVariables #-}
{-# Language TypeApplications    #-}

rotate :: forall a. Int -> [a] -> [a]
rotate = (<>) @(Int -> [a] -> [a]) drop take

Resolved using these instances:

instance Semigroup b => Semigroup (a -> b)
instance                Semigroup [a]
8

Two choices:

rotate = liftA2 (liftA2 (++)) drop take
rotate = getCompose (liftA2 (++) (Compose drop) (Compose take))

The latter becomes the former after inlining the instance method definitions for Compose's Applicative instance.

You may revert to spelling your liftA2s with (<$>) and (<*>) if you prefer it, of course.

2
  • 1
    You can use curry and uncurry instead of getCompose and Compose. Not sure if it's more readable or less :) Commented Aug 20, 2019 at 18:40
  • 3
    For the first, I've grown rather accustomed to the phrasing (liftA2 . liftA2) (++) drop take. It implies (correctly) that you can put as many liftA2s as you need to get an appropriate combinator.
    – luqui
    Commented Aug 21, 2019 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.