L04 ListZipper - Minimal traversing

[Riaan Rottier]

I am struggling with L04

-- Exercise 23
-- Relative Difficulty: 7
-- | Move the focus to the given absolute position in the zipper. Traverse the zipper only to the extent required.
--
-- >>> nth 1 (ListZipper [3,2,1] 4 [5,6,7])
-- [1]⋙2⋘[3,4,5,6,7]
--
-- >>> nth 5 (ListZipper [3,2,1] 4 [5,6,7])
-- [1,2,3,4,5]⋙6⋘[7]
--
-- >>> nth 8 (ListZipper [3,2,1] 4 [5,6,7])
-- ∅
nth ::
  ListZipper' f =>
  Int
  -> f a
  -> MaybeListZipper a
nth =
  error "todo"

My current approach is:

nth n lz = case toMaybeListZipper lz of
             IsZ (ListZipper l _ _) -> moveRightN (n - (length l)) lz
             IsNotZ                 -> IsNotZ

But this does not give you minimal traversing.  Anyone able to give me some clues as to how to approach this problem?

[Tony Morris]

I can tell you this much. This function is quite difficult. These is a handy function nearby iirc.

--
You received this message because you are subscribed to the Google Groups "haskell-exercises" group.
To unsubscribe from this group and stop receiving emails from it, send an email to haskell-exerci...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Jimmy P]

I guess he did only ask for a clue...

--

Cheers,

Jim P

@pjimmy

[Riaan Rottier]

Mmmm... I am wondering if I can upgrade that to a request for a hint...  Or a starting point for reasoning about the problem...

Still stumped.

R

[Tony Morris]

-- Exercise 21
-- Relative Difficulty: 6
-- | Move the focus left the given number of positions. If the value is
negative, move right instead.
-- If the focus cannot be moved, the given number of times, return the
value by which it can be moved instead.
--
-- >>> moveLeftN 2 (ListZipper [3,2,1] 4 [5,6,7])

-- [1]⋙2⋘[3,4,5,6,7]
--

-- >>> moveLeftN 4 (ListZipper [3,2,1] 4 [5,6,7])
-- ∅
--
-- >>> moveLeftN (-2) (ListZipper [3,2,1] 4 [5,6,7])

-- [1,2,3,4,5]⋙6⋘[7]
--

-- >>> moveLeftN (-4) (ListZipper [3,2,1] 4 [5,6,7])
-- ∅

On 25/07/13 12:48, Riaan Rottier wrote:
> Mmmm... I am wondering if I can upgrade that to a request for a hint... Or
> a starting point for reasoning about the problem...
>
> Still stumped.
>
> R
>
> On Thursday, July 25, 2013 8:22:24 AM UTC+10, Jimmy P wrote:
>> I guess he did only ask for a clue...
>>
>>
>> On 24 July 2013 19:29, Tony Morris <tmo...@tmorris.net <javascript:>>wrote:
>>
>>> I can tell you this much. This function is quite difficult. These is a
>>> handy function nearby iirc.

>>> On 24/07/2013 7:24 PM, "Riaan Rottier" <rrot...@rotnetix.com<javascript:>>

>>>> an email to haskell-exerci...@googlegroups.com <javascript:>.

>>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>>
>>>>
>>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "haskell-exercises" group.
>>> To unsubscribe from this group and stop receiving emails from it, send an

>>> email to haskell-exerci...@googlegroups.com <javascript:>.

>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>
>>>
>>>
>>
>>
>> --
>> Cheers,
>>
>> Jim P
>> @pjimmy
>>

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

[Riaan Rottier]

This function would still need to traverse all the way to the left end to know your current offset from the starting point so I don't see how that limits the extend you traverse the zipper any more than using (length l).

BTW. the examples below does not match the exercise.

[Tony Morris]

It would go all the way to the left, only if necessary. The necessary
case is if the zipper focus ultimately needs to not move or move to the
right to get to an absolute position.

Thanks for pointing out the problem on the tests.

[Riaan Rottier]

Still confused.  Let say:

nth 4 on [1]⋙2⋘[3,4,5,6,7]

you first need to know that you are at absolute position 1 in order to know that you need to go three to the right.  So you either call moveLeftN' 4 on it

and get back 1 which then tells you you are a position 1 and then you call moveLeftN' (1 - 4) which gets you to the absolute position 4.  In which case you traversed the same amount as if you have length l.

Alternatively you have 

nth 4 on [1,2,3,4,5]⋙6⋘[7] on which you call moveLeftN' 4 which returns another array which has [1]⋙2⋘[3,4,5,6,7], at this point you still don't know the absolute position so you need to call moveLeftN' 4 again which now returns moveLeftN' (1 - 4) which gets you to the absolute position 4.  In this case you have traverse 8 steps, using length l you traverse 6 steps, which is less than moveLeftN'.

Similarly is you have 

nth 1 on [1,2,3,4,5]⋙6⋘[7] the moveLeftN' will be less than the length l.

Or is there something I am completely missing?

[Tony Morris]

I think that makes sense.