Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there a workaround for the lack of type class backtracking?

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:

  • an (inefficient) default implementation is provided
  • if the user can provide some additional information about the type, we "unlock" a more efficient implementation

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?

like image 539
DanielM Avatar asked Feb 17 '15 21:02

DanielM


People also ask

How can we improve backtracking algorithm?

Backtracking algorithms can be improved by adding heuristics methods. You could add filtering and ordering techniques.

Which of the problems Cannot be solved by back backtracking method?

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.

What are the limitations of backtracking?

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.

What types of problems is the backtracking method of solving best suited for?

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


1 Answers

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"
like image 180
jberryman Avatar answered Oct 13 '22 14:10

jberryman