*Anonymous Coward*
2018-03-04 06:14:04.541669 UTC

1 | {- |

2 | data Ordering = LT | EQ | GT |

3 | together with a function |

4 | compare :: Ord a => a -> a -> Ordering |

5 | that decides if one value in an ordered type is less than ( LT ), equal to ( EQ ), or greater than ( GT ) another value. Using this function, redefine the function |

6 | occurs :: Ord a => a -> Tree a -> Bool for search trees. Why is this new definition more |

7 | efficient than the original version? |

8 | -} |

9 | |

10 | data Tree a = Leaf a | Node (Tree a) a (Tree a) |

11 | |

12 | -- Old definition |

13 | occurs :: Ord a => a -> Tree a -> Bool |

14 | occurs x (Leaf y) = x == y |

15 | occurs x (Node l y r) | x == y = True |

16 | | x < y = occurs x l |

17 | | otherwise = occurs x r |

18 | |

19 | |

20 | -- This version is more efficient becauseit only requires on comparison between x and y for each node, whereas the previous version may require two |

21 | occurs2 x (Leaf y) = x == y |

22 | occurs2 x (Node l y r) = case compare x y of |

23 | LT -> occurs x l |

24 | EQ -> True |

25 | GT -> occurs x r |