In this talk around the 1:20 mark, Edward Kmett mentions the lack of "type class backtracking" in Haskell. Consider the problem of "set equality" (where order and multiplicity are disregarded) implemented on lists:
equals :: [a] -> [a] -> Bool
By the nature of type classes I cannot provide an inefficient O(n²) comparison if all we have is Eq a
but efficiently compare the lists in O(n log n) if we have Ord a
.
I did understand why such a facility would be problematic. At the same time, Edward says that there are "tricks you could play" mentioning for instance type families.
Hence my question is, what would be a workaround to achieve the same effect:
This workaround does not necessarily need to use type classes.
Edit: Some people suggested simply providing equals
and efficientEquals
as two distinct methods. In general I agree that this is the more Haskell-idiomatic approach. However, I am not convinced that this is always possible. For instance, what if the equals method above is itself part of a type class:
class SetLike s where
equals :: Eq a => s a -> s a -> Bool
Assume that this class has been provided by someone else so I cannot simply add a new function to the typeclass. I now want to define the instance for []
. I know that []
can always provide an implementation of equals
no matter what constraints there are on a
but I cannot tell my instance to use the more efficient version if more information about a
is available.
Maybe I could wrap the list in a newtype and tag it with some additional type information?
Backtracking algorithms can be improved by adding heuristics methods. You could add filtering and ordering techniques.
Which of the problems cannot be solved by backtracking method? Explanation: N-queen problem, subset sum problem, Hamiltonian circuit problems can be solved by backtracking method whereas travelling salesman problem is solved by Branch and bound method. 2.
Backtracking • Disadvantages – Backtracking Approach is not efficient for solving strategic Problem. – The overall runtime of Backtracking Algorithm is normally slow – To solve Large Problem Sometime it needs to take the help of other techniques like Branch and bound.
Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time (by time, here, is referred to the time elapsed till reaching any level of the ...
In the scenario from your edit, you could use a GADT
as proof of your Ord
constraint:
{-# LANGUAGE GADTs #-}
import Data.List
class SetLike s where
equals :: Eq a => s a -> s a -> Bool
data OrdList a where
OrdList :: Ord a=> [a] -> OrdList a
instance SetLike OrdList where
equals (OrdList a) (OrdList b) = sort a == sort b
And for fun here's something that uses makes use of the OverlappingInstances
trick I mention in my comment. There are lots of ways to do this sort of thing:
{-# LANGUAGE DefaultSignatures, OverlappingInstances, UndecidableInstances, MultiParamTypeClasses, FlexibleInstances #-}
import Data.List
class Equals a where
equals :: [a] -> [a] -> Bool
default equals :: Ord a=> [a] -> [a] -> Bool
equals as bs = sort as == sort bs
instance Equals Int
instance Equals Integer
instance Equals Char
-- etc.
instance (Eq a)=> Equals a where
equals = error "slow version"
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With