Understanding toListOf with van Laarhoven traversals

Learn
#1

As a voluntary exercise I try to implement van Laarhoven lenses, prisms, traversals, folds and isos. For me, it’s all very abstract, but I feel like I’m making slow progress. Sometimes the intuition doesn’t work for me, then I try to let me guide by the types. When implementing toListOf I get stuck because “type tetris” doesn’t help anymore:

They start with

toListOf :: Traversal s s a a -> (s -> [a])

where a Traversal s t a b s is a function

forall f. Applicative f => (a -> f b) -> (s -> f t)

Then, they generalize Traversal s s a a to

(a -> Const (Endo [a]) a) -> (s -> Const (Endo [a]) s)

and this is the resulting function I try to implement:

toListOf :: ((a -> K (Endo [a]) a) -> (s -> K (Endo [a]) s)) -> (s -> [a])
toListOf t x = undefined

t is the “Traversal”, x is of type s and we expect a result of type [a].

My baby steps:

  • t expects a function from a to Const (Endo [a]) a, the only one I could think of is Const . Endo . map . const.
  • After applying t to it, I get a function
    foo = t $ Const . Endo . map . const :: s -> Const (Endo [a]) s
  • Then I have x as a value of type s and apply foo x, extract the value with getConst and finally get an
    Endo [a]

I have no idea how an Endo [a], a function [a] -> [a] helps me to get a final [a] value without having an initial list of a values. Can somebody give me some hints or point out mistakes I made before?

Thanks for your time!

1 Like
#2

I have no idea how an Endo [a], a function [a] -> [a] helps me to get a final [a] value without having an initial list of a values

How about apply the empty list ([]) to the function?

2 Likes
#3

My bad, I had a typo in toListOf's type. K is of course Const. Here’s a running but failing test, trying to prove that toListOf . elements = id on [Int]. It fails with the first non-empty list [0]:

module TinyLens where

import Data.Functor.Const ( Const(Const), getConst )
import Data.Semigroup ( Endo(Endo), appEndo )
import Test.QuickCheck ( quickCheck )

elements :: (Traversable t, Applicative f) => (a -> f b) -> (t a -> f (t b))
elements = traverse

toListOf :: ((a -> Const (Endo [a]) a) -> (s -> Const (Endo [a]) s)) -> (s -> [a])
toListOf t x =  let foo = t $ Const . Endo . map . const
                    bar = getConst $ foo x
                in  appEndo bar []

propSameList :: [Int] -> Bool
propSameList xs = toListOf elements xs == xs

main = quickCheck propSameList

Any ideas? Maybe my choice of foo is wrong?

#4

Hi @tomjaguarpaw, thank you for your time: it doesn’t work: Understanding toListOf with van Laarhoven traversals - #3 by memowe

#5

Yes, your choice of foo is wrong! I think perhaps the Endo is throwing you off. Endo is just used to get some increased performance here, it’s not essential. Try writing

toListOf :: ((a -> Const [a] a) -> (s -> Const [a] s)) -> (s -> [a])

and when you have that working you can try the version that uses Endo.

1 Like
#6

Maybe it is better to use DList a instead of Endo [a].

2 Likes
#7

Thank you, I think I saw difference lists before in LYAH. The signature is defined elsewhere so I can’t change it, but I’ll try to think it through with difference lists instead of lists! :slight_smile:

#8

Well OK, don’t change it then, instead write

anotherToListOf :: ((a -> Const [a] a) -> (s -> Const [a] s)) -> (s -> [a])

and once you have that working to your liking you can go back to the original question.

1 Like
#9

Thinking of lists instead of arbitrary Endo [a] functions via difference lists did the trick. Thank you so much, @tomjaguarpaw, @jaror and @Solid for helpful hints!

toListOf :: ((a -> Const (Endo [a]) a) -> (s -> Const (Endo [a]) s)) -> (s -> [a])
toListOf t x =  let aToFa = Const . Endo . (:)
                    sToFs = t aToFa
                    sEndo = getConst $ sToFs x
                in  appEndo sEndo []
1 Like
#10

You’re going into the right direction with appEndo bar []. It’s the
a -> Const (Endo [a]) a function that you should look into again.
Ignoring all of the newtype wrappers, what’s the most natural way to
turn an a into an arrow a -> [a] -> [a]? There’s a function I would
wager you know very well that has exactly that type signature!

EDIT: Mailing lists are slow; sorry for the noise on an already answered question :slight_smile:

1 Like
#11

No, I’m slow! Your hint was spot on!

Thank you all for your help without solving it completely for me. That’s a great learning experience. :heart:

2 Likes
#12

Nice! Good stuff. I’m glad you got it working.

1 Like