abstract "[state]" to "t state"

[arnemileswinter]

Hello thanks for this library :)

Do you think we could somehow abstract the [state] type for result paths?

If I'm not mistaken it could be a Monoid, Foldable instance, or possibly a custom Path typeclass with a predefined instance for [].

I'm thinking it might be helpful if the found path is to be reversed after it was found (and therefore couldve been constructed in a different order using for example :<| :|> from Data.Sequence), or within a monadic context some specialized type other than [state].

search-algorithms/src/Algorithm/Search.hs

Line 601 in 8defc3f

-> Maybe [state]

[devonhollowood]

I'm not opposed to this, but I don't have the time to implement it at the moment. I'd happily accept a PR, otherwise I will give it a shot when I have a chance. My preference would be to abstract it to Foldable -- what are your thoughts on that option vs. others?

My concerns are:

1. I'm not sure how invasive a change this will be. I suspect it won't be too bad, though.
2. I don't want this to be a breaking change for most users. My understanding is that this is only a breaking change for edge cases, but I would like to better understand that before implementing.

[arnemileswinter]

a Foldable instance definitely makes sense on the consumer side, whereas library-wise we'd need to somehow abstract over cons'ing path elements - i dont think Foldable has functions for this - maybe a Monoid makes sense but it might have overhead i think, because from what i know <> is more involved than :...

I see there's a benchmarking test-bed so that will be helpful.

Having written the issue i noticed a common pattern to skip reversing the found path is to simply swap the goal-state with the initial-state.
While this might work, I'm concerned that's mostly for textbook path finding problems such as maze solving and less where the goal state is an exploratory/pruned estimate such as in chess.

I'm considering writing a PR once my semester gets less cluttered, should be around february. :)

[devonhollowood]

Sounds good! Let me know if you start working on it, so that we don't duplicate our work.