Buchi automaton/ Finite State Machine implementation on haskell

Fairly new to Haskell and I must implement a buchi automaton

My original implementation was something like this

data NBA s a = NBA { states        :: [s];
                     finalStates   :: [s];
                     initialStates :: [s];
                     delta         :: Data.Map s [(a, s)]}

using Data.Map for the transition function. What said map is doing is returning, for a given state, a list that contains tuples (a, s) where a is an alphabet symbol and s is the destination state.

However I recently saw someone implementing automatons like

data NBA s a = NBA { states        :: [s];
                 finalStates   :: [s];
                 initialStates :: [s];
                 delta         :: s -> [(a, s)]}

which leaves the transition function to the user criteria where they can use whatever data structures they want. For dummy example they can even use pattern matching to define delta. Moreover all the functions working with buchi, for example, bfs can use delta automaton s to access all the states reachable from s, instead of using Map.lookup.

This left me wondering what is the most Haskellish way to make the Buchi automaton implementation?

One thing thak seems like a clear disadvantage of the second implementation is the removal of a state. Unless there is a different way to implement, for example, the deletion of a state

deleteState :: NBA -> s -> NBA
deleteState a s = { states = delete s (states a);
                    finalStates = delete s (states a);
                    initialStates = ...;
                    delta = filter (snd != s) (delta a)
                   }

In the new automaton every call to delta will always be accompanied by an application of filter.