Yes, having the implementation of Tape be { cur, left, right } can get rid
of the problem of avoiding an empty tape. There is an existing package
that implements that data type:
http://package.elm-lang.org/packages/wernerdegroot/listzipper/latest
(though imo there are still a few problems with that package's current
API). (Using a list zipper for you tape will also give you O(1) read/write
speed vs the O(log(n)) read/write speed of Array.)
However, you mentioned needing getTapeSymbol : Int -> Tape -> Char which
using a list zipper still won't help with (though it will guarantee the
tape isn't empty, so you would at least have a value on the tape to
possibly use as a default).
I'd be curious to see what the uses of getTapeSymbol are, since that will
be a trickier function to get rid of if it actually is needed by other
modules. I suspect looking into that further might reveal some assumptions
about the data that may be incorrect or may have implications that need to
be further considered. (For example, it seems like maybe you're trying to
keep references to points on the Tape? If so, what should happen to
references if the tape changes? That's seemingly safe since the tape can
only grow and never shrink, but what should happen if you try to use a
reference with a different tape? What if you later add features to Tape
that let it shrink; will you remember to reconsider all the assumptions
that references have been relying on?)
On Mon, Aug 21, 2017 at 1:56 PM, Dave Doty <pexa...@gmail.com> wrote:
> Talking through this helped me formulate a better strategy for at least
> this one problem, along the lines of Richard Feldman's talk "Making
> impossible states impossible": https://www.youtube.com/watch?v=IcgmSRJHu_8
>
> Instead of using an Array to represent the Tape, use a "current element"
> and two lists, e.g.,
>
> type alias Tape = { cur : Char, left : List Char, right : List Char}
>
> where cur represents the current element, and left and right are the
> portions of the tape on either side of cur (actually this trick of
> "represent one list with two stacks" is a common homework exercise).
>
> Maybe it's just a matter of me thinking harder about these situations.
>
>
> On Monday, August 21, 2017 at 1:41:55 PM UTC-7, Dave Doty wrote:
>>
>> Hi Aaron:
>>
>> Thanks for the ideas! I think they certainly can mitigate this concern in
>> many situations.
>>
>> For one situation I'm thinking of, I don't see how to apply these ideas.
>> I have a data structure backed by an Array. I carefully control how the
>> Array is accessed, so if I do my job correctly, I will never give it an
>> out-of-bounds index.
>>
>> Nonetheless, to access the Array, my code must call Array.get, which
>> returns a Maybe.
>>
>> Going with approach #1, giving a default value if the Array is accessed
>> out of bounds, worries me that if I DO introduce a bug that causes an Array
>> index out of bounds, this will mask the bug and make it difficult to track
>> down. If I actually made a coding mistake, I want the code to fail as close
>> as possible to the source of the bug.
>>
>> For approach #2, it's not clear how to scale that to something like, for
>> example, Array index out of bounds.
>>
>> Here's a decent minimal example: suppose you want to support access to a
>> sequence of values with a sort of "two-way iterator"; let's call the data
>> structure a "Tape" (the actual application I have in mind is a Turing
>> machine).
>>
>> The Tape is always non-empty, and has a leftmost value at position 0. The
>> client code should be able to access the value at the "current" position,
>> and to move the current position left or right. If it is 0 and they try to
>> move it left, it stays at 0. If it is on the last (rightmost) position of
>> the Array and they move it right, a new default element is appended to the
>> end. So client code can never cause the index to be invalid.
>>
>> Nonetheless, several times in my code I must access a value in the Tape,
>> and this is how I do it:
>>
>> getTapeSymbol : Int -> Tape -> Char
>> getTapeSymbol idx tape =
>> case Array.get idx tape of
>> Just ch ->
>> ch
>>
>> Nothing ->
>> Debug.crash ("The tape with contents '" ++ (String.fromList (
>> Array.toList tape)) ++ "' has been accessed with invalid index " ++
>> toString idx ++ ". There is a bug in the software. Please contact the
>> author.")
>>
>> The only alternative I see is to return a Maybe Char, and if Nothing
>> ever is returned, that implies there is a bug in my code and I can report
>> it to the user through the "normal" error message (the one that is normally
>> used to tell the user they made a mistake).
>>
>> I think I just talked myself into thinking that this is the reasonable
>> way to do it. But it does make me long for runtime exceptions for those
>> errors where you know that not only the current function, but also any
>> function that may have called it, really isn't going to be able to do any
>> error-handling or recovery more sophisticated than "print error message and
>> stack trace to screen".
>>
>> Dave
>>
>>
>>
>> On Sunday, August 20, 2017 at 9:50:00 PM UTC-7, Aaron VonderHaar wrote:
>>>
>>> I think there are two common approaches:
>>>
>>> 1) Deal with the Maybe at a different level. You mentioned having a
>>> deep call stack, and not wanting to pass a Maybe Int throughout, so maybe
>>> somewhere in the stack it makes sense to give a default value. Even though
>>> you know you have a non-empty list, it's likely that in certain contexts
>>> you *could* intelligibly deal with empty lists. Perhaps at a certain level
>>> there's an obvious default. For example, maybe at a relatively low level,
>>> it makes sense to default to zero if there are no items. Or if not, maybe
>>> you use the Int to make a String, and maybe it makes sense to default to
>>> the empty string or a placeholder if there's no max. Or if not, maybe the
>>> string is used in some Html and maybe it makes sense to show a different
>>> thing if there's no String.
>>>
>>> If there are any levels that have an obvious default, I think it can
>>> also improve the modularity and reusability of your code to implement those
>>> defaults even though you know in reality that code path will never get
>>> executed.
>>>
>>> 2) You said you had a provably non-empty list, so why not make a
>>> NonEmptyList type to represent that instead of using List. Then you could
>>> make `NonEmptyList.maximum : NonEmptyList Int -> Int` and not have to worry
>>> about Maybes.
>>>
>>> On Sun, Aug 20, 2017 at 1:12 PM, Dave Doty <pex...@gmail.com> wrote:
>>>
>>>> I have found many situations in which I am forced by the compiler to
>>>> deal with a situation that will never come up at runtime (or, if it does
>>>> come up, it's a bug in my code and not something the user can do to fix).
>>>> For example, I might make a provably non-empty List (e.g., it is
>>>> always made by the :: operator) and later ask for its max value:
>>>>
>>>> max: List Int -> Int
>>>> max list =
>>>> case List.maximum list of
>>>> Just v ->
>>>> v
>>>>
>>>> Nothing ->
>>>> Debug.crash "This should be unreachable."
>>>>
>>>> The "standard" way to handle this would be to make max return a Maybe
>>>> or a Result instead (i.e., just use List.maximum directly), but this
>>>> can have the effect of altering the type signature of several other
>>>> functions, all for an error that represents a bug in my program, not
>>>> something caused by user error that the user needs to be alerted about.
>>>> This might be 10 levels deep into a function call, and it seems dumb to
>>>> change the type signature of every function from max all the way back
>>>> up to the top to return Maybe, just to handle the situation (list is
>>>> empty) that can only arise through programmer error, not user error.
>>>>
>>>> Is there an "standard" way of dealing with situations like this? I
>>>> assume it's not Debug.crash, given the ample warnings against using it
>>>> in production code. But despite the advertisements of "no runtime
>>>> exceptions in practice", sometimes it seems that there really is no
>>>> graceful way to handle programming errors other than to tell the user
>>>> there's a bug in the code, and dump a stack trace so that the bug can be
>>>> tracked down. In other words, a runtime exception seems like it does
>>>> exactly what is needed in this situation.
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Elm Discuss" group.
>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>> an email to elm-discuss...@googlegroups.com.
>>>> For more options, visit https://groups.google.com/d/optout.
>>>>
>>>
>>> --
> You received this message because you are subscribed to the Google Groups
> "Elm Discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to elm-discuss+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>
--
You received this message because you are subscribed to the Google Groups "Elm
Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to elm-discuss+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
