2

I have large and complex immutable data structure (language is F#, but should be applicable to any language really) where I defined a lot of functions making changes and returning new instances of ds with signatures like:

val action: ... -> ds:Ds<U> -> Ds<U> 

What I want is to somehow abstract the changes that happened in datastructure after series of different actions, so that my UI controls / supporting data structures will have a "delta" that they can use to efficiently update. Without the "delta", recomputing all these data from the ground up would be much more costly.

A simple example would be a normal immutable list datastructure with inserts and removes. If this data structure is used as a backing data of ListBox in UI, I would want to be notified of changes like item A was removed, item B was added to quickly update my ListBox instead of clearing the control and filling it again after each ds update.

How would you approach such a problem?

  • What's wrong with your "simple example" ? – Mike Nakis Jul 26 '16 at 7:26
2

I sketch a possible approach. I would first define the operations that are expected to be applied to your data structure (if I understand correctly, you have already done this). Using Haskell notation (I am not familiar with F#, I hope the Haskell notation is intuitive enough for you) for lists you would have:

add    ::         a -> [a] -> [a]
remove :: Eq a => a -> [a] -> [a]

where I assume that add is just the cons operation (:), and remove is a function that removes the first occurrence of the specified element. So, in Haskell these are already standard functions:

import Data.List(delete)

add    = (:)
remove = delete

Then I would use a data type for log entries:

data Action a = Add a | Remove a

So the source of changes to your data structure outputs a stream of actions on some specific type. If your list contains strings, you have

actions :: [Action String]

Your update function will be

update :: Eq a => Action a -> [a] -> [a]
update (Add x)    = add x
update (Remove x) = remove x
...

Summarizing:

  1. You define the elementary operations on your data structure and try to find an efficient implementation for them. You could find interesting ideas in Purely Functional Data Structures.
  2. You define log entries as a data type with one data constructor per operation.
  3. You define the source of your actions as producing a stream of log entries.
  4. All places in your code that need to react to actions take a stream of log entries as input and process log entries using the update function as soon as they are available.

For simplicity's sake, I have defined the source of actions as a (lazy, possibly infinite) list. This would imply that consumers of the actions would have to pull log entries from their source. In a GUI application you would rather want to push log entries from their source to the various GUI components that need to be updated.

So, that last aspect you may need to consider is how to make your application reactive. (Maybe you have already solved this in your application, I just add some hints for completeness.) What you need is to turn your infinite list (stream) of log entries into an observable, and let the consumers of the observable apply the update function to their local copy of the data structure. In case you are interested, there is sufficient information about reactive programming in F# on the net, see e.g. this article.

  • Very nice. I was also thinking of using Writer monad to return list of changes from every update function, but this "inverted" solution seems much simpler. – ghord Jul 26 '16 at 10:22
  • What about complex operations which are typically composed from multiple smaller operations? – ghord Jul 26 '16 at 10:27
  • @ghord: Maybe you can define log entries for complex operations and then implement the update function accordingly: update (Complex x) = (simple2 . simple1) x. Or just add an extra operation complex = simple2 . simple1 and define update (Complex x) = complex x. – Giorgio Jul 26 '16 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.