L04 ListZipper - Extend

29 views
Skip to first unread message

Riaan Rottier

unread,
Jul 27, 2013, 11:23:24 PM7/27/13
to haskell-...@googlegroups.com
I am still busy with ListZipper and now I am stuck at extend:

-- Exercise 36
-- Relative Difficulty: 7
-- | Implement the `Extend` instance for `ListZipper`.
-- This implementation "visits" every possible zipper value derivable from a given zipper (i.e. all zippers to the left and right).
--
-- /Tip:/ Use @Data.List#unfoldr@.
--
-- >>> id <<= (ListZipper [2,1] 3 [4,5])
-- [[]⋙1⋘[2,3,4,5],[1]⋙2⋘[3,4,5]]⋙[1,2]⋙3⋘[4,5]⋘[[1,2,3]⋙4⋘[5],[1,2,3,4]⋙5⋘[]]

I have done this a while back but have completely forgotten even how to get started. Could someone perhaps point me in the right direction?

Thanks 
Riaan

Tony Morris

unread,
Jul 27, 2013, 11:40:17 PM7/27/13
to haskell-...@googlegroups.com
Perhaps one additional tip to the one given (use unfoldr) is to perhaps
conceptualise it differently. Consider the function duplicate:

duplicate :: ListZipper a -> ListZipper (ListZipper a)
duplicate = extend id

extend :: (ListZipper a -> b) -> ListZipper a -> ListZipper b
extend f = fmap f . duplicate

You can see that you can write duplicate and extends in terms of each
other, so if you can write one, you can easily recover the other.

Therefore, perhaps think of the problem in terms of duplicate. The
duplicate function takes a zipper and produces a zipper that contains
all possible zippers. You can get all these zippers by moving left and
right from the original zipper. Sometimes you won't be able to move
left/right because you at the end. The move function will return Maybe.
That's when you want to stop producing zippers. Maybe is also used to
indicate to unfoldr to stops producing values.

--
Tony Morris
http://tmorris.net/

Riaan Rottier

unread,
Jul 28, 2013, 6:10:42 AM7/28/13
to haskell-...@googlegroups.com, tmo...@tmorris.net
Thanks, that helps a lot.

R
Reply all
Reply to author
Forward
0 new messages