I would argue that there's no such thing as a "functional data structure." If a data structure maps poorly to existing functional languages, that's a symptom of an insufficiently powerful and generic type system.

Say you have (pseudocode)

  Array(4 16 5 20)

What's its type?

  Array
  Array<Int>
  Array<4>
  Array<Int 4>
  Array(Int Int Int Int)

None of these lend themselves easily to paradigms other than imperative, true. But this is because they unnecessarily discard known information. The type of an array ought to be itself:

  assert Array(4 16 5 20) hasType Array(4 16 5 20)
    => Ok
  
  assert Array(4 16 5 20) hasType Array<Int>
    => Error("Expected Array<Int> but got Array(4 16 5 20). Hint: Typeclass Array<Int> cannot be directly instantiated")
  
  assert Array(4 16 5 20) hasTypeclass Array<Int>
    => Ok

Fully functional and referentially transparent.