search

devonhollowood / search-algorithms

Haskell library containing common graph search algorithms
BSD 3-Clause "New" or "Revised" License
51 stars 2 forks source link

abstract "[state]" to "t state" #16

Open arnemileswinter opened 2 years ago

arnemileswinter commented 2 years ago

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].

https://github.com/devonhollowood/search-algorithms/blob/8defc3ff88639e3ae78f20767cda0bc9046b97c7/src/Algorithm/Search.hs#L601

devonhollowood commented 2 years ago

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 commented 2 years ago

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 commented 2 years ago

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