I think using existential types will give you data-hiding like this. (Disclaimer: I'm still learning about them, and making up this syntax.) Say my abstract data type is

    DijkstraLib =
    there exists GraphState with {
        construct: List(Edge) -> GraphState
        getDist: GraphState -> Vertex -> Vertex -> Num
    }

Now we can write two different implementations of this type that use a different data structure for graph. The data structure will be opaque to the client (even though the client obtains and passes around graph objects!). Like so:

    -- Library
    type CachingDijkstraLib : DijkstraLib
    with GraphState = (HashMap((Vertex, Vertex), Num), List(Edge))
    with {
        construct(a_list) = (HashMap.empty, a_list)
        ...
    }

    -- Client
    DL = CachingDijkstraLib : DijkstraLib
    some_obj = DL.construct(edge_list)
    DL.getDist(some_obj, u, v)
    DL2 = SomeOtherDijkstraLib : DijkstraLib
    some_other_obj = DL2.construct(edge_list)
    DL2.getDist(some_other_obj, u, v)

The types of some_obj and some_other_obj could be completely different, and neither would be accessible to the client. For example, the client couldn't assume some_obj is a pair and try to get its first element. It would also be an error to call e.g. DL2.getDist(some_obj, ...).