/usr/share/doc/libghc-hashable-doc/html/src/Data-Hashable.html is in libghc-hashable-doc 1.2.6.1-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 | <?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<!-- Generated by HsColour, http://code.haskell.org/~malcolm/hscolour/ -->
<title>Data/Hashable.hs</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
<pre><a name="line-1"></a><span class='hs-comment'>{-# LANGUAGE CPP #-}</span>
<a name="line-2"></a><span class='hs-comment'>{-# LANGUAGE DeriveDataTypeable #-}</span>
<a name="line-3"></a><span class='hs-cpp'>#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 702</span>
<a name="line-4"></a><span class='hs-comment'>{-# LANGUAGE Trustworthy #-}</span>
<a name="line-5"></a><span class='hs-cpp'>#endif</span>
<a name="line-6"></a>
<a name="line-7"></a><span class='hs-comment'>------------------------------------------------------------------------</span>
<a name="line-8"></a><span class='hs-comment'>-- |</span>
<a name="line-9"></a><span class='hs-comment'>-- Module : Data.Hashable</span>
<a name="line-10"></a><span class='hs-comment'>-- Copyright : (c) Milan Straka 2010</span>
<a name="line-11"></a><span class='hs-comment'>-- (c) Johan Tibell 2011</span>
<a name="line-12"></a><span class='hs-comment'>-- (c) Bryan O'Sullivan 2011, 2012</span>
<a name="line-13"></a><span class='hs-comment'>-- License : BSD-style</span>
<a name="line-14"></a><span class='hs-comment'>-- Maintainer : johan.tibell@gmail.com</span>
<a name="line-15"></a><span class='hs-comment'>-- Stability : provisional</span>
<a name="line-16"></a><span class='hs-comment'>-- Portability : portable</span>
<a name="line-17"></a><span class='hs-comment'>--</span>
<a name="line-18"></a><span class='hs-comment'>-- This module defines a class, 'Hashable', for types that can be</span>
<a name="line-19"></a><span class='hs-comment'>-- converted to a hash value. This class exists for the benefit of</span>
<a name="line-20"></a><span class='hs-comment'>-- hashing-based data structures. The module provides instances for</span>
<a name="line-21"></a><span class='hs-comment'>-- most standard types. Efficient instances for other types can be</span>
<a name="line-22"></a><span class='hs-comment'>-- generated automatically and effortlessly using the generics support</span>
<a name="line-23"></a><span class='hs-comment'>-- in GHC 7.2 and above.</span>
<a name="line-24"></a><span class='hs-comment'>--</span>
<a name="line-25"></a><span class='hs-comment'>-- The easiest way to get started is to use the 'hash' function. Here</span>
<a name="line-26"></a><span class='hs-comment'>-- is an example session with @ghci@.</span>
<a name="line-27"></a><span class='hs-comment'>--</span>
<a name="line-28"></a><span class='hs-comment'>-- > ghci> import Data.Hashable</span>
<a name="line-29"></a><span class='hs-comment'>-- > ghci> hash "foo"</span>
<a name="line-30"></a><span class='hs-comment'>-- > 60853164</span>
<a name="line-31"></a>
<a name="line-32"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Hashable</span>
<a name="line-33"></a> <span class='hs-layout'>(</span>
<a name="line-34"></a> <span class='hs-comment'>-- * Hashing and security</span>
<a name="line-35"></a> <span class='hs-comment'>-- $security</span>
<a name="line-36"></a>
<a name="line-37"></a> <span class='hs-comment'>-- * Computing hash values</span>
<a name="line-38"></a> <span class='hs-conid'>Hashable</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span>
<a name="line-39"></a>
<a name="line-40"></a> <span class='hs-comment'>-- * Creating new instances</span>
<a name="line-41"></a> <span class='hs-comment'>-- | There are two ways to create new instances: by deriving</span>
<a name="line-42"></a> <span class='hs-comment'>-- instances automatically using GHC's generic programming</span>
<a name="line-43"></a> <span class='hs-comment'>-- support or by writing instances manually.</span>
<a name="line-44"></a>
<a name="line-45"></a> <span class='hs-comment'>-- ** Generic instances</span>
<a name="line-46"></a> <span class='hs-comment'>-- $generics</span>
<a name="line-47"></a>
<a name="line-48"></a> <span class='hs-comment'>-- *** Understanding a compiler error</span>
<a name="line-49"></a> <span class='hs-comment'>-- $generic_err</span>
<a name="line-50"></a>
<a name="line-51"></a> <span class='hs-comment'>-- ** Writing instances by hand</span>
<a name="line-52"></a> <span class='hs-comment'>-- $blocks</span>
<a name="line-53"></a>
<a name="line-54"></a> <span class='hs-comment'>-- *** Hashing contructors with multiple fields</span>
<a name="line-55"></a> <span class='hs-comment'>-- $multiple-fields</span>
<a name="line-56"></a>
<a name="line-57"></a> <span class='hs-comment'>-- *** Hashing types with multiple constructors</span>
<a name="line-58"></a> <span class='hs-comment'>-- $multiple-ctors</span>
<a name="line-59"></a>
<a name="line-60"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>hashUsing</span>
<a name="line-61"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>hashPtr</span>
<a name="line-62"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>hashPtrWithSalt</span>
<a name="line-63"></a><span class='hs-cpp'>#if defined(__GLASGOW_HASKELL__)</span>
<a name="line-64"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>hashByteArray</span>
<a name="line-65"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>hashByteArrayWithSalt</span>
<a name="line-66"></a><span class='hs-cpp'>#endif</span>
<a name="line-67"></a> <span class='hs-comment'>-- * Caching hashes</span>
<a name="line-68"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>Hashed</span>
<a name="line-69"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>hashed</span>
<a name="line-70"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>unhashed</span>
<a name="line-71"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>mapHashed</span>
<a name="line-72"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>traverseHashed</span>
<a name="line-73"></a> <span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-74"></a>
<a name="line-75"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Hashable</span><span class='hs-varop'>.</span><span class='hs-conid'>Class</span>
<a name="line-76"></a>
<a name="line-77"></a><span class='hs-cpp'>#ifdef GENERICS</span>
<a name="line-78"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Hashable</span><span class='hs-varop'>.</span><span class='hs-conid'>Generic</span> <span class='hs-conid'>()</span>
<a name="line-79"></a><span class='hs-cpp'>#endif</span>
<a name="line-80"></a>
<a name="line-81"></a><span class='hs-comment'>-- $security</span>
<a name="line-82"></a><span class='hs-comment'>-- #security#</span>
<a name="line-83"></a><span class='hs-comment'>--</span>
<a name="line-84"></a><span class='hs-comment'>-- Applications that use hash-based data structures to store input</span>
<a name="line-85"></a><span class='hs-comment'>-- from untrusted users can be susceptible to \"hash DoS\", a class of</span>
<a name="line-86"></a><span class='hs-comment'>-- denial-of-service attack that uses deliberately chosen colliding</span>
<a name="line-87"></a><span class='hs-comment'>-- inputs to force an application into unexpectedly behaving with</span>
<a name="line-88"></a><span class='hs-comment'>-- quadratic time complexity.</span>
<a name="line-89"></a><span class='hs-comment'>--</span>
<a name="line-90"></a><span class='hs-comment'>-- At this time, the string hashing functions used in this library are</span>
<a name="line-91"></a><span class='hs-comment'>-- susceptible to such attacks and users are recommended to either use</span>
<a name="line-92"></a><span class='hs-comment'>-- a 'Data.Map' to store keys derived from untrusted input or to use a</span>
<a name="line-93"></a><span class='hs-comment'>-- hash function (e.g. SipHash) that's resistant to such attacks. A</span>
<a name="line-94"></a><span class='hs-comment'>-- future version of this library might ship with such hash functions.</span>
<a name="line-95"></a>
<a name="line-96"></a><span class='hs-comment'>-- $generics</span>
<a name="line-97"></a><span class='hs-comment'>--</span>
<a name="line-98"></a><span class='hs-comment'>-- Beginning with GHC 7.2, the recommended way to make instances of</span>
<a name="line-99"></a><span class='hs-comment'>-- 'Hashable' for most types is to use the compiler's support for</span>
<a name="line-100"></a><span class='hs-comment'>-- automatically generating default instances.</span>
<a name="line-101"></a><span class='hs-comment'>--</span>
<a name="line-102"></a><span class='hs-comment'>-- > {-# LANGUAGE DeriveGeneric #-}</span>
<a name="line-103"></a><span class='hs-comment'>-- ></span>
<a name="line-104"></a><span class='hs-comment'>-- > import GHC.Generics (Generic)</span>
<a name="line-105"></a><span class='hs-comment'>-- > import Data.Hashable</span>
<a name="line-106"></a><span class='hs-comment'>-- ></span>
<a name="line-107"></a><span class='hs-comment'>-- > data Foo a = Foo a String</span>
<a name="line-108"></a><span class='hs-comment'>-- > deriving (Eq, Generic)</span>
<a name="line-109"></a><span class='hs-comment'>-- ></span>
<a name="line-110"></a><span class='hs-comment'>-- > instance Hashable a => Hashable (Foo a)</span>
<a name="line-111"></a><span class='hs-comment'>-- ></span>
<a name="line-112"></a><span class='hs-comment'>-- > data Colour = Red | Green | Blue</span>
<a name="line-113"></a><span class='hs-comment'>-- > deriving Generic</span>
<a name="line-114"></a><span class='hs-comment'>-- ></span>
<a name="line-115"></a><span class='hs-comment'>-- > instance Hashable Colour</span>
<a name="line-116"></a><span class='hs-comment'>--</span>
<a name="line-117"></a><span class='hs-comment'>-- If you omit a body for the instance declaration, GHC will generate</span>
<a name="line-118"></a><span class='hs-comment'>-- a default instance that correctly and efficiently hashes every</span>
<a name="line-119"></a><span class='hs-comment'>-- constructor and parameter.</span>
<a name="line-120"></a>
<a name="line-121"></a><span class='hs-comment'>-- $generic_err</span>
<a name="line-122"></a><span class='hs-comment'>--</span>
<a name="line-123"></a><span class='hs-comment'>-- Suppose you intend to use the generic machinery to automatically</span>
<a name="line-124"></a><span class='hs-comment'>-- generate a 'Hashable' instance.</span>
<a name="line-125"></a><span class='hs-comment'>--</span>
<a name="line-126"></a><span class='hs-comment'>-- > data Oops = Oops</span>
<a name="line-127"></a><span class='hs-comment'>-- > -- forgot to add "deriving Generic" here!</span>
<a name="line-128"></a><span class='hs-comment'>-- ></span>
<a name="line-129"></a><span class='hs-comment'>-- > instance Hashable Oops</span>
<a name="line-130"></a><span class='hs-comment'>--</span>
<a name="line-131"></a><span class='hs-comment'>-- And imagine that, as in the example above, you forget to add a</span>
<a name="line-132"></a><span class='hs-comment'>-- \"@deriving 'Generic'@\" clause to your data type. At compile time,</span>
<a name="line-133"></a><span class='hs-comment'>-- you will get an error message from GHC that begins roughly as</span>
<a name="line-134"></a><span class='hs-comment'>-- follows:</span>
<a name="line-135"></a><span class='hs-comment'>--</span>
<a name="line-136"></a><span class='hs-comment'>-- > No instance for (GHashable (Rep Oops))</span>
<a name="line-137"></a><span class='hs-comment'>--</span>
<a name="line-138"></a><span class='hs-comment'>-- This error can be confusing, as 'GHashable' is not exported (it is</span>
<a name="line-139"></a><span class='hs-comment'>-- an internal typeclass used by this library's generics machinery).</span>
<a name="line-140"></a><span class='hs-comment'>-- The correct fix is simply to add the missing \"@deriving</span>
<a name="line-141"></a><span class='hs-comment'>-- 'Generic'@\".</span>
<a name="line-142"></a>
<a name="line-143"></a><span class='hs-comment'>-- $blocks</span>
<a name="line-144"></a><span class='hs-comment'>--</span>
<a name="line-145"></a><span class='hs-comment'>-- To maintain high quality hashes, new 'Hashable' instances should be</span>
<a name="line-146"></a><span class='hs-comment'>-- built using existing 'Hashable' instances, combinators, and hash</span>
<a name="line-147"></a><span class='hs-comment'>-- functions.</span>
<a name="line-148"></a><span class='hs-comment'>--</span>
<a name="line-149"></a><span class='hs-comment'>-- The functions below can be used when creating new instances of</span>
<a name="line-150"></a><span class='hs-comment'>-- 'Hashable'. For example, for many string-like types the</span>
<a name="line-151"></a><span class='hs-comment'>-- 'hashWithSalt' method can be defined in terms of either</span>
<a name="line-152"></a><span class='hs-comment'>-- 'hashPtrWithSalt' or 'hashByteArrayWithSalt'. Here's how you could</span>
<a name="line-153"></a><span class='hs-comment'>-- implement an instance for the 'B.ByteString' data type, from the</span>
<a name="line-154"></a><span class='hs-comment'>-- @bytestring@ package:</span>
<a name="line-155"></a><span class='hs-comment'>--</span>
<a name="line-156"></a><span class='hs-comment'>-- > import qualified Data.ByteString as B</span>
<a name="line-157"></a><span class='hs-comment'>-- > import qualified Data.ByteString.Internal as B</span>
<a name="line-158"></a><span class='hs-comment'>-- > import qualified Data.ByteString.Unsafe as B</span>
<a name="line-159"></a><span class='hs-comment'>-- > import Data.Hashable</span>
<a name="line-160"></a><span class='hs-comment'>-- > import Foreign.Ptr (castPtr)</span>
<a name="line-161"></a><span class='hs-comment'>-- ></span>
<a name="line-162"></a><span class='hs-comment'>-- > instance Hashable B.ByteString where</span>
<a name="line-163"></a><span class='hs-comment'>-- > hashWithSalt salt bs = B.inlinePerformIO $</span>
<a name="line-164"></a><span class='hs-comment'>-- > B.unsafeUseAsCStringLen bs $ \(p, len) -></span>
<a name="line-165"></a><span class='hs-comment'>-- > hashPtrWithSalt p (fromIntegral len) salt</span>
<a name="line-166"></a>
<a name="line-167"></a><span class='hs-comment'>-- $multiple-fields</span>
<a name="line-168"></a><span class='hs-comment'>--</span>
<a name="line-169"></a><span class='hs-comment'>-- Hash constructors with multiple fields by chaining 'hashWithSalt':</span>
<a name="line-170"></a><span class='hs-comment'>--</span>
<a name="line-171"></a><span class='hs-comment'>-- > data Date = Date Int Int Int</span>
<a name="line-172"></a><span class='hs-comment'>-- ></span>
<a name="line-173"></a><span class='hs-comment'>-- > instance Hashable Date where</span>
<a name="line-174"></a><span class='hs-comment'>-- > hashWithSalt s (Date yr mo dy) =</span>
<a name="line-175"></a><span class='hs-comment'>-- > s `hashWithSalt`</span>
<a name="line-176"></a><span class='hs-comment'>-- > yr `hashWithSalt`</span>
<a name="line-177"></a><span class='hs-comment'>-- > mo `hashWithSalt` dy</span>
<a name="line-178"></a><span class='hs-comment'>--</span>
<a name="line-179"></a><span class='hs-comment'>-- If you need to chain hashes together, use 'hashWithSalt' and follow</span>
<a name="line-180"></a><span class='hs-comment'>-- this recipe:</span>
<a name="line-181"></a><span class='hs-comment'>--</span>
<a name="line-182"></a><span class='hs-comment'>-- > combineTwo h1 h2 = h1 `hashWithSalt` h2</span>
<a name="line-183"></a>
<a name="line-184"></a><span class='hs-comment'>-- $multiple-ctors</span>
<a name="line-185"></a><span class='hs-comment'>--</span>
<a name="line-186"></a><span class='hs-comment'>-- For a type with several value constructors, there are a few</span>
<a name="line-187"></a><span class='hs-comment'>-- possible approaches to writing a 'Hashable' instance.</span>
<a name="line-188"></a><span class='hs-comment'>--</span>
<a name="line-189"></a><span class='hs-comment'>-- If the type is an instance of 'Enum', the easiest path is to</span>
<a name="line-190"></a><span class='hs-comment'>-- convert it to an 'Int', and use the existing 'Hashable' instance</span>
<a name="line-191"></a><span class='hs-comment'>-- for 'Int'.</span>
<a name="line-192"></a><span class='hs-comment'>--</span>
<a name="line-193"></a><span class='hs-comment'>-- > data Color = Red | Green | Blue</span>
<a name="line-194"></a><span class='hs-comment'>-- > deriving Enum</span>
<a name="line-195"></a><span class='hs-comment'>-- ></span>
<a name="line-196"></a><span class='hs-comment'>-- > instance Hashable Color where</span>
<a name="line-197"></a><span class='hs-comment'>-- > hashWithSalt = hashUsing fromEnum</span>
<a name="line-198"></a><span class='hs-comment'>--</span>
<a name="line-199"></a><span class='hs-comment'>-- If the type's constructors accept parameters, it is important to</span>
<a name="line-200"></a><span class='hs-comment'>-- distinguish the constructors. To distinguish the constructors, add</span>
<a name="line-201"></a><span class='hs-comment'>-- a different integer to the hash computation of each constructor:</span>
<a name="line-202"></a><span class='hs-comment'>--</span>
<a name="line-203"></a><span class='hs-comment'>-- > data Time = Days Int</span>
<a name="line-204"></a><span class='hs-comment'>-- > | Weeks Int</span>
<a name="line-205"></a><span class='hs-comment'>-- > | Months Int</span>
<a name="line-206"></a><span class='hs-comment'>-- ></span>
<a name="line-207"></a><span class='hs-comment'>-- > instance Hashable Time where</span>
<a name="line-208"></a><span class='hs-comment'>-- > hashWithSalt s (Days n) = s `hashWithSalt`</span>
<a name="line-209"></a><span class='hs-comment'>-- > (0::Int) `hashWithSalt` n</span>
<a name="line-210"></a><span class='hs-comment'>-- > hashWithSalt s (Weeks n) = s `hashWithSalt`</span>
<a name="line-211"></a><span class='hs-comment'>-- > (1::Int) `hashWithSalt` n</span>
<a name="line-212"></a><span class='hs-comment'>-- > hashWithSalt s (Months n) = s `hashWithSalt`</span>
<a name="line-213"></a><span class='hs-comment'>-- > (2::Int) `hashWithSalt` n</span>
</pre></body>
</html>
|