# CIS 194 | Help on non-exhaustive pattern

**URL:** <https://discourse.haskell.org/t/cis-194-help-on-non-exhaustive-pattern/8347>\
**Category:** Learn\
**Created:** [December 18, 2023, 1:20pm UTC](https://discourse.haskell.org/t/cis-194-help-on-non-exhaustive-pattern/8347 "2023-12-18T13:20:36Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![jfvillablanca](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jfvillablanca/32/3942_2.png) [@jfvillablanca](https://discourse.haskell.org/u/jfvillablanca)\
**Post date:** [December 18, 2023, 1:20pm UTC](https://discourse.haskell.org/t/cis-194-help-on-non-exhaustive-pattern/8347/1 "2023-12-18T13:20:36Z")

</div>

Super new to Haskell and I’m loving the language.  
I’m doing the homework exercises in CIS194, particularly, [Homework 2 - Exercise 2](https://www.seas.upenn.edu/~cis1940/spring13/hw/02-ADTs.pdf),

Lecture 2 provides Log.hs and I am to write LogAnalysis.hs

Log.hs

```haskell
-- CIS 194 Homework 2

module Log where

import Control.Applicative

data MessageType = Info
                 | Warning
                 | Error Int
  deriving (Show, Eq)

type TimeStamp = Int

data LogMessage = LogMessage MessageType TimeStamp String
                | Unknown String
  deriving (Show, Eq)

data MessageTree = Leaf
                 | Node MessageTree LogMessage MessageTree
  deriving (Show, Eq)

-- | @testParse p n f@ tests the log file parser @p@ by running it
-- on the first @n@ lines of file @f@.
testParse :: (String -> [LogMessage])
          -> Int
          -> FilePath
          -> IO [LogMessage]
testParse parse n file = take n . parse <$> readFile file

-- | @testWhatWentWrong p w f@ tests the log file parser @p@ and
-- warning message extractor @w@ by running them on the log file
-- @f@.
testWhatWentWrong :: (String -> [LogMessage])
                  -> ([LogMessage] -> [String])
                  -> FilePath
                  -> IO [String]
testWhatWentWrong parse whatWentWrong file
  = whatWentWrong . parse <$> readFile file

```

I already accomplished exercise 1

```haskell
{-# OPTIONS_GHC -Wall #-}

module LogAnalysis where

import Log

-- Exercise 1
parseMessage :: String -> LogMessage
parseMessage strLog = case words strLog of
    ("I" : ts : logString) ->
      LogMessage Info (read ts) (unwords logString)
    ("W" : ts : logString) ->
      LogMessage Warning (read ts) (unwords logString)
    ("E" : etype : ts : logString) ->
      LogMessage (Error (read etype)) (read ts) (unwords logString)
    _ -> Unknown strLog

parse :: String -> [LogMessage]
parse strLogs = map parseMessage (lines strLogs)

```

and now for exercise 2, i am to insert `LogMessage` nodes to a `MessageTree` binary search tree

this is my implementation currently

```haskell
-- Exercise 2
insert :: LogMessage -> MessageTree -> MessageTree
insert (Unknown _) msgTree = msgTree
insert logMsg@(LogMessage{}) Leaf = Node Leaf logMsg Leaf
insert 
  logMsg@(LogMessage _ ts _) 
  (Node leftTree nodeLogMsg@(LogMessage _ nodeTs _) rightTree)
    | ts < nodeTs = Node (insert logMsg leftTree) nodeLogMsg rightTree
    | otherwise = Node leftTree nodeLogMsg (insert logMsg rightTree)

```

To my problem, ghci is warning me on ‘incomplete-patterns’

```haskell
LogAnalysis.hs:20:1: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘insert’:
        Patterns of type ‘LogMessage’, ‘MessageTree’ not matched:
            (LogMessage _ _ _) (Node _ (Unknown _) _)
   |
20 | insert (Unknown _) msgTree = msgTree
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...

```

But from my understanding of my implementation, all `LogMessage`s of `Unknown` types wouldn’t be inserted in a `MessageTree` in the first place. I understand that the compiler might not be able to infer this runtime behavior but is there a way to “tell” the compiler that I don’t have to match that pattern?

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [December 18, 2023, 1:24pm UTC](https://discourse.haskell.org/t/cis-194-help-on-non-exhaustive-pattern/8347/2 "2023-12-18T13:24:17Z")

</div>

The most straightforward way would be to define a new data type for log messages that doesn’t have the `Unknown` constructor, for example:

```haskell
data KnownLogMessage = KnownLogMessage MessageType TimeStamp String
  deriving (Show, Eq)

data MessageTree = Leaf
                 | Node MessageTree KnownLogMessage MessageTree

```

EDIT: corrected thanks to @jaror

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [December 18, 2023, 1:26pm UTC](https://discourse.haskell.org/t/cis-194-help-on-non-exhaustive-pattern/8347/3 "2023-12-18T13:26:28Z")

</div>

If you are very confident that you are correct then you can just use `error`:

```haskell
insert LogMessage{} (Node _ Unknown{} _) =
  error "impossible: unknown node in log messages"

```

---

<div class="post-metadata">

**Author:** ![jackdk](https://avatars.discourse-cdn.com/v4/letter/j/9f8e36/32.png) [@jackdk](https://discourse.haskell.org/u/jackdk)\
**Post date:** [December 18, 2023, 10:29pm UTC](https://discourse.haskell.org/t/cis-194-help-on-non-exhaustive-pattern/8347/4 "2023-12-18T22:29:51Z")

</div>

While you can probably get away with `error` here, you don’t know that you’re the only one creating `MessageTree`s. Someone could construct a broken tree and crash your program. If I was doing this exercise “for real”, I’d use @tomjaguarpaw’s approach, and probably also change the `LogMessage` constructor to `LogMessage KnownLogMessage`.

Another alternative is to return `Maybe MessageTree`, and return `Nothing` when the tree contains unexpected nodes, but that a) pushes more responsibility downstream (though this is not too bad, after you pick up the tools provided by `Functor`/`Applicative`/`Monad`) and b) breaks the written constraints of the exercise.

---

<div class="post-metadata">

**Author:** ![rhendric](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/rhendric/32/2689_2.png) [@rhendric](https://discourse.haskell.org/u/rhendric)\
**Post date:** [December 18, 2023, 11:26pm UTC](https://discourse.haskell.org/t/cis-194-help-on-non-exhaustive-pattern/8347/5 "2023-12-18T23:26:52Z")

</div>

I’m surprised to find myself in disagreement with the other posters here! You can make `insert` a total function (no incomplete warnings, no use of `error` or `undefined`) without changing any types or changing its behavior on the subset of `msgTree`s that don’t contain `Unknown`:

```haskell
insert (Unknown _) msgTree = msgTree
insert logMsg@(LogMessage{}) Leaf = Node Leaf logMsg Leaf
insert 
  logMsg@(LogMessage _ ts _) 
  (Node leftTree nodeLogMsg@(LogMessage _ nodeTs _) rightTree)
    | ts < nodeTs = Node (insert logMsg leftTree) nodeLogMsg rightTree
insert logMsg (Node leftTree nodeLogMsg rightTree) = 
  Node leftTree nodeLogMsg (insert logMsg rightTree)

```

A set of guards (`| ts < nodeTs`) doesn’t have to be exhaustive in Haskell, as long as the overall set of patterns is. If that guard is reached and `ts` is not less than `nodeTs`, the program will proceed to checking the next function clause.

---

<div class="post-metadata">

**Author:** ![jfvillablanca](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jfvillablanca/32/3942_2.png) [@jfvillablanca](https://discourse.haskell.org/u/jfvillablanca)\
**Post date:** [December 19, 2023, 11:37am UTC](https://discourse.haskell.org/t/cis-194-help-on-non-exhaustive-pattern/8347/6 "2023-12-19T11:37:39Z")

</div>

Thank you everyone for the help! I learned a lot. I wouldn’t have thought to construct a new data type, or use `error` as a catch. I was thinking about using `Maybe` to unwrap the value though.

@rhendric’s solution seems to be the one I’m looking for. I just thought that guards needed the `otherwise` branch in order for the function to be total.

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [December 19, 2023, 12:57pm UTC](https://discourse.haskell.org/t/cis-194-help-on-non-exhaustive-pattern/8347/7 "2023-12-19T12:57:57Z")

</div>

> [@tomjaguarpaw](#):
>
> ```haskell
> data MessageTree = Leaf
> | Node KnownMessageTree LogMessage KnownMessageTree
> 
> ```

Is this a typo? I think you meant:

```haskell
data MessageTree = Leaf
                 | Node MessageTree KnownLogMessage MessageTree

```

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [December 19, 2023, 12:59pm UTC](https://discourse.haskell.org/t/cis-194-help-on-non-exhaustive-pattern/8347/8 "2023-12-19T12:59:51Z")

</div>

Oh thanks, that’s what I should have written.

---

<div class="post-metadata">

**Author:** ![Esnos33](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/esnos33/32/3915_2.png) [@Esnos33](https://discourse.haskell.org/u/Esnos33)\
**Post date:** [December 19, 2023, 5:22pm UTC](https://discourse.haskell.org/t/cis-194-help-on-non-exhaustive-pattern/8347/9 "2023-12-19T17:22:58Z")

</div>

I have just added `insert _ tree = tree` at the end like this:

```haskell
insert :: LogMessage -> MessageTree -> MessageTree
insert (Unknown _) tree = tree
insert message Leaf = Node Leaf message Leaf
insert message (Node left treeMessage right)
  | getTime message <= getTime treeMessage = Node (insert message left) treeMessage right
  | getTime message > getTime treeMessage = Node left treeMessage (insert message right)
insert _ tree = tree

```

This is good catch all metod.

---

<div class="post-metadata">

**Author:** ![jackdk](https://avatars.discourse-cdn.com/v4/letter/j/9f8e36/32.png) [@jackdk](https://discourse.haskell.org/u/jackdk)\
**Post date:** [December 20, 2023, 12:23am UTC](https://discourse.haskell.org/t/cis-194-help-on-non-exhaustive-pattern/8347/10 "2023-12-20T00:23:03Z")

</div>

If you evolve the data types, this function will silently ignore new constructors, which might not be what you want. I generally prefer (when it’s not too hard) to enumerate a set of patterns which cover all cases, so that when I change a type, the compiler reminds me to consider each use site.