Haskell — CWE-407 Language Analysis
=====================================

.. contents:: :local:

Overview
--------

Haskell's ``elem :: Eq a => a -> [a] -> Bool`` function (and its operator form `` x \`elem\` xs ``)
performs a linear scan of a list. This is O(n) by definition — Haskell lists are singly-linked,
so membership can only be determined by traversal. The function is universally available and
idiomatically natural; this makes it the canonical CWE-407 source in Haskell.

The fix is to use ``Data.Set.member :: Ord a => a -> Set a -> Bool`` (O(log n), balanced BST)
or ``Data.HashMap.Strict.member :: (Eq k, Hashable k) => k -> HashMap k v -> Bool`` (O(1)
amortized). For the specific use case of cycle detection and visited-node tracking, neither the
ordering constraint of ``Data.Set`` nor the ``Hashable`` constraint of ``Data.HashMap`` is
onerous — node identity (``Eq``, ``Ord``, or explicit node IDs) is always available.

GHC itself carries four instances of this defect: see :doc:`../compiler/ghc`.

Canonical Defect Pattern
------------------------

.. code-block:: haskell

   -- Defective — O(V²)
   import Data.List (elem)

   dfs :: Graph -> [Vertex] -> Vertex -> [Vertex]
   dfs graph visited v
     | v `elem` visited = visited           -- O(|visited|) per call
     | otherwise = foldl (dfs graph) (v : visited) (neighbors graph v)

.. code-block:: haskell

   -- Fixed — O(V log V) with Data.Set
   import qualified Data.Set as Set

   dfs :: Graph -> Set.Set Vertex -> Vertex -> Set.Set Vertex
   dfs graph visited v
     | Set.member v visited = visited       -- O(log V) per call
     | otherwise = foldl (dfs graph)
                         (Set.insert v visited)
                         (neighbors graph v)

.. code-block:: haskell

   -- Fixed — O(V) with Data.HashMap (if Hashable instance available)
   import qualified Data.HashMap.Strict as HashMap

   dfs :: Graph -> HashMap.HashMap Vertex () -> Vertex -> HashMap.HashMap Vertex ()
   dfs graph visited v
     | HashMap.member v visited = visited   -- O(1) amortized
     | otherwise = foldl (dfs graph)
                         (HashMap.insert v () visited)
                         (neighbors graph v)

Confirmed Defects
-----------------

Four defects in GHC, covering SCC decode, edge-existence testing, register allocation, and
type-class constructor checking. All unpatched. See :doc:`../compiler/ghc` for full analysis.

| Defect  | File                                    | Complexity          | Status    |
|---------|-----------------------------------------|---------------------|-----------|
| ghc-0001| ``Directed/Internal.hs:78``             | O(V × degree)       | Unpatched |
| ghc-0002| ``Inductive/Graph.hs:489-501``          | O(degree) per query | Unpatched |
| ghc-0003| ``Graph/Ops.hs:637``                    | O(deg²) per func    | Unpatched |
| ghc-0004| ``Tc/TyCl/Utils.hs:973``               | O(V²)               | Unpatched |

Ecosystem Note
--------------

GHC's own internal use of ``elem`` for cycle detection is ironic: the compiler that compiles
Haskell programs carries the canonical Haskell O(n) membership defect. The ``Data.Graph`` module
in the Haskell ``containers`` library (which GHC bundles) is correctly implemented using arrays
and integer indices — GHC's defective sites are in the middle-end compiler passes, not in the
base library.

Note: Erlang OTP's ``beam_digraph.erl`` (internal VM module, OTP 22+) is correctly implemented
with maps/sets. The defective sites are in the ``digraph`` and ``digraph_utils`` stdlib modules
that predate OTP 22.

References
----------

* :doc:`../compiler/ghc`
