2

Is there a type in Haskell where is absolutely needed to use bottom value i.e. undefined? Or it is just used to get the code compiling while the code is in process?

I thought maybe exist a rare type that needs undefined to finish its construction, lists needs only 1:[] and that's it, but maybe a data type is complex enough to need undefined` to finish its construction.

Is there more complex constructor that need undefined to be typed?

3
  • 1
    I'm not sure I understand the question yet. Is your question whether there is any type for which any term that has that type is bottom? Or are you asking whether there is any type where idiomatic use of that type involves a bottom somewhere? Or something else...? Aug 17, 2019 at 0:37
  • @DanielWagner thanks a lot! with you questions I could find some really nice info. Aug 17, 2019 at 2:22
  • here's what looks like one example. :) empty tree would be empty = Node 0 undefined undefined. (Of course one could put anything there, including empty or Node 10000000 empty empty; it's not a good design.)
    – Will Ness
    Aug 20, 2019 at 15:15

2 Answers 2

2

Sometimes, you want to pass a value just to pass the type of that value, while you don't care about the actual value. Take for example asTypeOf :: a -> a -> a. It does not examine is seconds argument, it's just there to set the type a:

Prelude> maxBound `asTypeOf` (0::Word)
18446744073709551615
Prelude> maxBound `asTypeOf` (0::Int)
9223372036854775807
Prelude> maxBound `asTypeOf` (undefined::Int)
9223372036854775807

As you see, asTypeOf works perfectly with undefined being passed as value for its second argument, because any Int-typed value will cause maxBound to be taken as maxBound for Int.

You might argue that it is a stupid idea to pass a value to asTypeOf which you never use. That type feels wrong. Instead, you just need to pass something carrying the type information. There are implementations of a Proxy type using that idea, although the standard version of Proxy is slightly different. A simple Proxy implementation could work like this:

-- Note: No data constructor at all.
-- This type is uninhabitated, the only possible value is undefined
data Proxy a

-- generator function for a proxy value. As there is no value, it has to return
-- undefined.
proxy :: Proxy a
proxy = undefined

asProxiedBy :: a -> Proxy a -> a
asProxiedBy x _ = x

With this code, you can write

*Main> maxBound `asProxiedBy` (proxy :: Proxy Int)
9223372036854775807

In this revised example, replace asTypeOf by asProxiedBy, you no longer pass an unused value, but instead you passed the undefined value as reference type. To avoid to spell the ugly word undefined, the method proxy has been introduced to generate undefined values of all Proxy types.

3
  • 2
    Yeah, but you really shouldn't use that sort of proxy, because it makes you use undefined!
    – dfeuer
    Aug 17, 2019 at 1:37
  • 7
    The usual definition of proxies has data Proxy a = Proxy. The whole point of the pattern is to use Proxy -- a fully-defined value -- instead of undefined, thus making it possible to entirely avoid needing undefined. Aug 17, 2019 at 3:03
  • 1
    In modern Haskell, I believe there's little need for asTypeOf, if any. Writing x :: T is now always possible thanks to ScopedTypeVariables, and that documents the intended type better than x `asTypeOf` y, where you need y to be of the intended type. We never had to use ``x asTypeOf (undefined :: T)` since that would be equivalent to x :: T, we needed asTypeOf when we could not write T explicitly, but we had a value of that type at hand, IIRC.
    – chi
    Aug 17, 2019 at 8:04
1

Finally I found some examples where undefined can fit:

newtype Wrap = W {w :: Wrap} deriving Show

www = W $ W $ W $ undefined

and you can count them (with no end):

count :: Wrap -> Int
count (W a) = count a + 1

Here, Wrap needs undefined to end.

class Peano a where
    zero :: a
    next :: a -> a


alt_zero, alt_one, alt_two, alt_three :: (Peano a) => a
alt_zero = undefined
alt_one = next alt_zero -- = succ undefined
alt_two = next alt_one -- = succ (succ undefined)
alt_three = next alt_two -- = succ (succ (succ undefined))

here you can create 1, 2, 3 without instance, or you can give a concrete type also.

data Nat = Z | S Nat deriving Show

instance (Peano Nat) where
  zero = Z
  next = S

instance (Peano Wrap) where
  zero = undefined
  next = W

countN :: Nat -> Int 
countN Z = 0
countN (S n) = (countN n) + 1

And some implementations. I knew if I search a little more I would find something

9
  • Or data Void = Void !Void, or if you don't care about Haskell 98, data Void. But these are boring. There are much more interesting uses of bottom out there. Look at the definition I wrote for Data.Sequence.zipWith.
    – dfeuer
    Aug 17, 2019 at 2:32
  • @dfeuer indeed there are! l = Seq $ Deep 3 (One (Elem (1,2))) EmptyT (Two undefined (Elem (5,6))) Aug 17, 2019 at 2:42
  • Wrap does not need undefined to end: x = W x is not bottom (and does not contain bottom anywhere inside). Perhaps you intended it to be a newtype instead? Aug 17, 2019 at 2:48
  • @Daniel Wagner indeed, you are right like always :). Isn’t that the same as ‘n = n + 1’? Aug 17, 2019 at 2:54
  • 1
    Yes, W is a function. But data constructors are special: they mark places where evaluation to WHNF is permitted to stop. Mere non-constructor function applications do not share this property. See also "guarded recursion"; x = W x is guarded, while x = 1 + x is not. Aug 17, 2019 at 5:28

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.