Stepanov Andrew :: Recent Entries

Title:	Exercise 16.39, page 327
Topics:	haskell
Date:	2009-11-04 @ 20:43
Security:	public

Задание звучит как:

Give an implementation of the Set abstract data type (ADT) using search trees.

Для примера, автор в книге, в качестве хранилища для Set использует обычные списки. Читателя просит не меняя экспортированного интерфейса для Set, заменить незаметно для пользователя реализацию, используя деревья.
Search trees - это тоже ADT. Как реализованы деревья нас не волнует. Мы только знаем о деревьях что слева от узла, расположены узлы с меньшим значением, а справа от узла - узлы с большим значением.

Запинка была только при реализации функций diff, union, inter(section). Довольно интересно находить пересечение, объединение и одностороннюю разницу для деревьев.

Решение задачки: http://pastebin.com/f1958340d
Где использовался ADT деревьев из главы выше: http://pastebin.com/f661dae06


*Ex16d39> showSet show $ diff (makeSet [1,2,3,4,5,100,111]) (makeSet [5,4,3,2,1,10,11])
"100 111 "
*Ex16d39> showSet show $ union (makeSet [1,2,3,4,5,100,111]) (makeSet [5,4,3,2,1,10,11])
"1 2 3 4 5 10 11 100 111 "
*Ex16d39> showSet show $ inter (makeSet [1,2,3,4,5,100,111]) (makeSet [5,4,3,2,1,10,11])
"1 2 3 4 5 "

:: +Memory :: :: Reply

Title:	diff
Topics:	haskell
Date:	2009-10-29 @ 00:11
Security:	public

-- Задачка простая в доску: для списка A вывести элементы которые отсутствуют в списке B.

-- Стандартная функция (\\) из Data.List нам не подходит, так как она не учитывает тот факт,
-- что элементы в списке могут повторяться. Например:

[2,2,1,4] \\ [2,1]

-- результат: [2,4]. Двойки быть не должно.

--- Мое решение:

foldr (\ x -> filter (/=x)) [2,2,1,4] [2,1]

-- получим [4]

foldl (flip (\ x -> filter (/=x))) [2,2,1,4] [2,1]

-- получим [4]

:: +Memory :: :: 1 reply :: Reply

Title:	Задачка!
Topics:	haskell
Date:	2009-10-27 @ 01:09
Security:	public

-- Предлагаю решить задачку :)
-- А именно: роставить типы для выражений после `where`.

powerSet :: Ord a => Set a -> Set (Set a)
powerSet (SetI [])     = SetI [SetI []]
powerSet (SetI (x:xs)) = union replicateWithX subsets
    where
    subsets                = powerset (seti xs)
    replicateWithX         = mapSet addElem subsets
    addElem (SetI sub)     = SetI (x:sub)

-- Предупреждаю сразу: у меня не получилось.
-- Без указания типов - программа работает как ожидается.

-- Например:
    where
    subsets :: Set (Set a)
    subsets                = powerset (seti xs)
-- будем посланы подальше.

-- Полиморфному типу передается другой полиморфный тип.

-- Дополнительная информация:

newtype Set a = SetI [a]

makeSet :: Ord a => [a] -> Set a
makeSet = SetI . remDups . sort
          where
          remDups []     = []
          remDups [x]    = [x]
          remDups (x:y:xs)
           | x < y     = x : remDups (y:xs)
           | otherwise = remDups (y:xs)

mapSet :: Ord b    => (a -> b) -> Set a -> Set b
mapSet f (SetI xs) = makeSet (map f xs)

-- > :t union
-- union :: (Ord a) => Set a -> Set a -> Set a

-- Или работающий исходный код целиком: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=11188#a11188

:: +Memory :: :: 4 replies :: Reply

Title:	Опасность алиасов
Topics:	haskell
Date:	2009-10-22 @ 19:18
Security:	public

Haskell умный, не позволяет себя обмануть.

В первом случае:

> class Class f where
>  foo :: f a b -> Bool

> data Type a = No | Yes a

> type Alias a b = Type (a,b)

> instance A Alias where
>  foo _ = True

И во втором:

> class Class f where
>  foo :: f a -> Bool

> data Type a b = No | Yes a b

> type Alias a = Type a a

> instance B Alias where
>  foo _ = True

Будем посланы поназначенью.

:: +Memory :: :: Reply

Title:	Exercise 16.30, page 320
Topics:	haskell
Date:	2009-10-22 @ 13:49
Security:	public

Надеюсь упражнение не прошло даром.
Exercise 16.30

:: +Memory :: :: 1 reply :: Reply

Title:	Полиморфизм
Topics:	haskell
Date:	2009-10-21 @ 15:25
Security:	public

Может когда нить я пойму почему нельзя писать:

class MyClass functor where
foo :: functor -> Bool
boo :: functor a -> a

Нужно забить на полиморфизм, и вернутся к нему спустя некоторое время.

:: +Memory :: :: 4 replies :: Reply

Title:	Опять полиморфизм.
Topics:	haskell
Date:	2009-10-21 @ 12:09
Security:	public

Мозгу сложно понять.

> class Test f where
>   foo :: f a -> b

> data MyType a = Cons a Int

> instance Test MyType where
>  foo (Cons a x) = (a,x)

ab.hs:7:18:
    Couldn't match expected type `b' against inferred type `(a, Int)'
      `b' is a rigid type variable bound by
          the type signature for `foo' at ab.hs:2:15
    In the expression: (a, x)
    In the definition of `foo': foo (Cons a x) = (a, x)
    In the definition for method `foo'
Failed, modules loaded: none.

Я хотел сказать что 'b' может принимать значение любого типа.
Вот именно, 'b' может принимать значение любого типа, но тип '(a, Int)' уже не любой тип.
Проблема состоит в том, что 'b' - не только может быть любым типом, но и ОБЯЗАНО быть любым типом.

В качестве 'b' можно вернуть только:

> undefined
> error

Prelude> :t error
error :: [Char] -> a

Prelude> :t undefined
undefined :: a

Так что тело функции не имеет свободу выбора, она должна возвращать любой тип, в буквальном смысле.

11:22 < blackh> stanv: Without adding something to the 'class' declaration, you can't return anything as b.
Как это понять?

Аналогично:

> class Test f where
>  foo :: (Num b) => f a -> b

> data MyType a = Cons a Int

> instance Test MyType where
>  foo (Cons x y) = y

ab.hs:7:18:
    Couldn't match expected type `b' against inferred type `Int'
      `b' is a rigid type variable bound by
          the type signature for `foo' at ab.hs:2:13
    In the expression: y
    In the definition of `foo': foo (Cons x y) = y
    In the definition for method `foo'
Failed, modules loaded: none.

Как я предпологаю, тип Int не является любым типом класса Num.

Ха-ха.

:: +Memory :: :: 1 reply :: Reply

Title:	Почувствуй разницу
Topics:	haskell
Date:	2009-10-21 @ 01:04
Security:	public

data MyType1 a = Constructor1 a deriving (Show)
data MyType2 a b = Constructor2 (a,b) deriving (Show)

class MyClass1 f where
foo :: (a,b) -> f (a,b) -> f (a,b)

class MyClass2 f where
boo :: (a,b) -> f a b -> f a b

instance MyClass1 MyType1 where
foo z (Constructor1 _) = Constructor1 z

instance MyClass2 MyType2 where
boo z (Constructor2 _) = Constructor2 z

:: +Memory :: :: Reply

Title:	О полиморфных функциях
Topics:	haskell
Date:	2009-10-20 @ 15:47
Security:	public

Оказывается невозможно использовать pattern matching в полиморфных функциях:

>   data MyType a = Constructor a

>   class MyClass f where
>      foo :: a -> f a -> f a

>   instance MyClass MyType where
>      foo (x,y) (Constructor (_,_)) = Constructor (x,y)

Prelude> :r
[1 of 1] Compiling Main             ( quest.hs, interpreted )

quest.hs:7:5:
    Couldn't match expected type `a' against inferred type `(t, t1)'
      `a' is a rigid type variable bound by
          the type signature for `foo' at quest.hs:4:8
    In the pattern: (x, y)
    In the definition of `foo':
        foo (x, y) (Constructor (_, _)) = Constructor (x, y)
    In the definition for method `foo'
Failed, modules loaded: none.

Не прокатит и такой вариант:

>   data MyType a = Constructor a

>   class MyClass f where
>      foo :: a -> f a -> f a

>   instance MyClass MyType where
>      foo z (Constructor _) = Constructor (x,y)
>       where
>        (x,y) = z

quest.hs:9:11:
    Couldn't match expected type `(t, t1)' against inferred type `a'
      `a' is a rigid type variable bound by
          the type signature for `foo' at quest.hs:4:8
    In the expression: z
    In a pattern binding: (x, y) = z
    In the definition of `foo':
        foo z (Constructor _)
              = Constructor (x, y)
              where
                  (x, y) = z
Failed, modules loaded: none.

Implementation для функции foo должно быть полностью полиморфным относительно `a'.
Полиморфные функции с параметром не позволяют определять какой в действительности тип они получили.
Они должны отрабатывать единым образом для всех типов.
Т.е. я не знаю что `z' это пара. Signature для функции `foo' позволяет быть `a' чем угодно.

:: +Memory :: :: 2 replies :: Reply

Title:	Алиасы
Topics:	haskell
Date:	2009-10-20 @ 11:38
Security:	public

Оказывается можно создавать алиасы для будь каких типов.
Раньше я писал:

>   type Pair = (Int, String)

Но Haskell понимает и такой синтаксис алиасов:

>   type AnyPair a b = (a,b)

Тогда в сигнатуре функции необходимо задавать:

>   eq :: (Eq a) => AnyPair a b -> AnyPair a b -> Bool
>   eq p1 p2 = fst p1 == fst p2

*Main> eq (1,"a") (1,"b")
True

Интересно можно ли в алиасе задавать требование принадлежности типов к классам?

:: +Memory :: :: 1 reply :: Reply