Haskell: cache result of a function in pattern matching

Question

I have the following algebraic data type:

data Tree a = Empty | Node a (Tree a) (Tree a)
  deriving (Show, Eq)

Also, I have

data Step = StepL | StepR
  deriving (Show, Eq)

Now, I need a function search that takes

1. a root of the tree
2. a target value t ... and it must return a path of type [Step] leading to a node with value t. Also, if t is not present in the tree, search must return Nothing. Finally, the input is guaranteed to have the target value at most once.

My best effort, as of now, is:

searchHelper :: Eq a => a -> Tree a -> [Step] -> Maybe [Step]
searchHelper _ Empty _ = Nothing
searchHelper targetValue (Node nodeValue leftChild rightChild) stepsSoFar = 
  if targetValue == nodeValue then Just stepsSoFar 
  else if searchHelper targetValue leftChild (stepsSoFar ++ [StepL]) /= Nothing then searchHelper targetValue leftChild (stepsSoFar ++ [StepL])
  else if searchHelper targetValue rightChild (stepsSoFar ++ [StepR]) /= Nothing then searchHelper targetValue rightChild (stepsSoFar ++ [StepR])
  else Nothing

search :: Eq a => a -> Tree a -> Maybe [Step]
search targetValue root = searchHelper targetValue root []

As you can see, I call the searchHelper too often (else if searchHelper targetValue leftChild (stepsSoFar ++ [StepL]) /= Nothing then searchHelper targetValue leftChild (stepsSoFar ++ [StepL])). I need a machinery that would allow me to cache the results of searchHelper calls and use them in if ... then ... else.

Q: How can I do it?

Answer 1

The use of the word cache confused me, but if I understand the question correctly, the real problem is the repeated use of the same expression. That could certainly become a readability and maintainability issue in a larger code base, so is worthwhile addressing.

From the context this looks like a 'toy problem'. There's nothing wrong with that - I play with plenty of those myself to learn new stuff. The reason I mention it, though, is that from this and other clues I gather that you're still a Haskell beginner. Again: nothing wrong with that, but it just means that I'm going to skip some of the slightly more advanced Haskell stuff.

Checking for Nothing or Just like in the OP is rarely idiomatic Haskell. Instead you'd use pattern-matching or (more commonly) some of the higher-level APIs for working with Maybe (such as Functor, Applicative, Monad, etc.).

That said, I gather that this isn't quite what you need right now. In order to cut down on the duplication of expressions, you can use let..in syntax in Haskell:

searchHelper :: Eq a => a -> Tree a -> [Step] -> Maybe [Step]
searchHelper _ Empty _ = Nothing
searchHelper targetValue (Node nodeValue leftChild rightChild) stepsSoFar = 
  if targetValue == nodeValue then Just stepsSoFar
  else
    let l = searchHelper targetValue leftChild (stepsSoFar ++ [StepL])
    in if l /= Nothing then l
  else
    let r = searchHelper targetValue rightChild (stepsSoFar ++ [StepR])
    in if r /= Nothing then r
  else Nothing

This enables you to 'declare' 'variables' l and r and reuse them.

As my lengthy preamble suggests, this still isn't idiomatic Haskell, but I hope it adresses the immediate question.