Haskell: cache result of a function in pattern matching

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?

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.

I'd like to propose a dissenting answer. The answer to the general question is indeed to use let (or where) to name the computation, and refer to that name twice. But the answer to this specific question is to dissolve the problem. Instead of:

if {- X -} /= Nothing then {- X -} else {- Y -}

use a case to inspect X and dispatch on its value. Like this:

case {- X -} of
    Nothing -> {- Y -}
    Just v -> Just v

This Just v -> Just v is very readable, but it does have an unfortunate operational interpretation: destructure the Maybe value, then immediately build a new Maybe value that's exactly the same. Rather than allocating a fresh value, you can simply return the one you've got using as-patterns: the pattern var@pat (where var is a variable name and pat is a pattern) matches exactly when pat matches, but also binds the name var to the entire value that was matched. So:

case {- X -} of
    Nothing -> {- Y -}
    v@(Just _) -> v

If we were to apply this pattern of rewrite to your original code, here's where we'd land:

searchHelper targetValue (Node nodeValue leftChild rightChild) stepsSoFar = 
  if targetValue == nodeValue then Just stepsSoFar 
  else case searchHelper targetValue leftChild (stepsSoFar ++ [StepL]) of
         Nothing -> case searchHelper targetValue rightChild (stepsSoFar ++ [StepR]) of
           Nothing -> Nothing
           v@(Just _) -> v
         v@(Just _) -> v

This rewrite reveals something quite nice: the inside case always returns the exact thing it sees! So we can simply return the exact thing it sees directly, without ever inspecting it with case.

searchHelper targetValue (Node nodeValue leftChild rightChild) stepsSoFar = 
  if targetValue == nodeValue then Just stepsSoFar 
  else case searchHelper targetValue leftChild (stepsSoFar ++ [StepL]) of
         Nothing -> searchHelper targetValue rightChild (stepsSoFar ++ [StepR])
         v@(Just _) -> v

This would be a fine spot for a beginner to stop. For an expert, I would expect at this point to notice that the case used above is an instance of the (<|>) function, defined so for Maybe values:

Nothing <|> r = r
l       <|> _ = l

So:

searchHelper targetValue (Node nodeValue leftChild rightChild) stepsSoFar = 
  if targetValue == nodeValue then Just stepsSoFar 
  else searchHelper targetValue leftChild (stepsSoFar ++ [StepL])
   <|> searchHelper targetValue rightChild (stepsSoFar ++ [StepR])

In this particular case, I think I would also consider converting the first part of the if to a bare Maybe value so that I could chain <|>s. That would give you one of these (asum is the listified form of chaining <|>s):

-- the empty is just to make the following lines more uniform, it should be compiled away
searchHelper targetValue (Node nodeValue leftChild rightChild) stepsSoFar = empty
  <|> (stepsSoFar <$ guard (targetValue == nodeValue))
  <|> searchHelper targetValue leftChild (stepsSoFar ++ [StepL])
  <|> searchHelper targetValue rightChild (stepsSoFar ++ [StepR])

-- OR:
searchHelper targetValue (Node nodeValue leftChild rightChild) stepsSoFar = asum
  [ stepsSoFar <$ guard (targetValue == nodeValue)
  , searchHelper targetValue leftChild (stepsSoFar ++ [StepL])
  , searchHelper targetValue rightChild (stepsSoFar ++ [StepR])
  ]

This fully addresses your original concern. To be really thorough with my suggestions, I'd also want to see stepsSoFar get built up in reverse; repeatedly prepending to a list is much cheaper than repeatedly appending.

searchHelper targetValue (Node nodeValue leftChild rightChild) stepsSoFar = asum
  [ reverse stepsSoFar <$ guard (targetValue == nodeValue)
  , searchHelper targetValue leftChild (StepL : stepsSoFar)
  , searchHelper targetValue rightChild (StepR : stepsSoFar)
  ]

At this point, I would consider this quite idiomatic Haskell. Whether the repetition in the final two elements of the asum bothers you is an aesthetic choice that I could see two experts disagreeing on. If it bothers you, it could be addressed like this:

searchHelper targetValue (Node nodeValue leftChild rightChild) stepsSoFar =
  (reverse stepsSoFar <$ guard (targetValue == nodeValue))
  <|>
    [ searchHelper targetValue child (step : stepsSoFar)
    | (child, step) <- [(leftChild, StepL), (rightChild, StepR)]
    ]

Personally I find the additional complexity not worth the sharing, so I would skip this change. (Actually, to be completely fair, I would probably make this change, look at it, and then revert it. ^_^)