evgenii-malov’s gists

evgenii-malov / segment_tree.hs

Last active April 7, 2022 14:54

segment tree build and query

	-- video https://www.youtube.com/watch?v=nckWiHmeNXU&feature=youtu.be
	{-# LANGUAGE RankNTypes #-}
	-- GHCi, version 8.8.4
	-- data Btree a = Empty \| Node a (Btree a) (Btree a) deriving Show
	-- https://www.youtube.com/watch?v=Ud-1Z0hBlB8&t=379s

	-- data Btree a = Empty \| Node a (Btree a) (Btree a) deriving Show
	{-# OPTIONS_GHC -Wno-incomplete-patterns #-}
	import PrettyT -- https://www.youtube.com/watch?v=Ud-1Z0hBlB8&t=3s
	import Data.List.Split (chunksOf, whenElt)

evgenii-malov / merkle_tree.hs

Created April 1, 2022 16:43

merkle tree and merkle path build and transaction in a block proof function

	-- GHCi, version 8.8.4
	-- data Btree a = Empty \| Node a (Btree a) (Btree a) deriving Show
	import PrettyT -- https://www.youtube.com/watch?v=Ud-1Z0hBlB8&t=379s
	import Data.Hashable
	import Data.List.Split

	h v = show $ hash v

	merkle :: (String -> String) -> [String] -> Btree String
	merkle h d = go nl

evgenii-malov / tries.hs

Last active March 26, 2022 07:10

Tries with haskell | hashmap based on trie | insert | delete | search

	-- GHCi, version 8.8.4
	{-# LANGUAGE ExistentialQuantification #-}
	{-# LANGUAGE InstanceSigs #-}
	{-# LANGUAGE FlexibleInstances #-}
	{-# LANGUAGE ScopedTypeVariables #-}
	{-# LANGUAGE MultiParamTypeClasses #-}
	import Data.List
	import Data.Maybe
	import Data.Tree
	data Trie k v = Nd (Maybe k) (Maybe v) [Trie k v] deriving Show

evgenii-malov / kd_tree.hs

Last active March 24, 2022 11:38

Build balanced k-d tree and range search with Haskell

	-- GHCi, version 8.8.4
	-- watch video https://www.youtube.com/watch?v=kYxOabjYWgc
	{-# LANGUAGE ScopedTypeVariables #-}
	{-# LANGUAGE ExistentialQuantification #-}
	{-# LANGUAGE FunctionalDependencies #-}
	{-# LANGUAGE FlexibleInstances #-}

	import PrettyT -- https://www.youtube.com/watch?v=Ud-1Z0hBlB8&t=379s
	import Data.List as L
	import Data.Maybe

evgenii-malov / 2sum_eq_k.hs

Last active March 24, 2022 11:39

find two numbers in a sorted list wich sum equals to k

	-- GHCi, version 8.8.4
	-- video https://www.youtube.com/watch?v=JPikTujq6mw&t=2839s
	import Data.Maybe
	import Data.List
	-- given an ordered list of numbers and number k
	-- find 2 numbers x and y such as x+y=k

	-- input: [-2,-1,1,4,7,8,12,13] k = 9
	-- output: 1,8

evgenii-malov / find_ps.hs

Last active March 24, 2022 11:40

find a predicessor and succesor in an ordered list with haskell

	-- GHCi, version 8.8.4
	-- explain video - https://www.youtube.com/watch?v=oCiR3Rk7H_Y&t=1390s
	import Data.Maybe
	-- https://www.geeksforgeeks.org/inorder-predecessor-successor-given-key-bst/
	-- predecessor and succesor of an element in a sorted list (no duplicates)

	--staightforward solution - get lower elements and extract maximum
	-- find predecessor
	fp :: Ord a => [a] -> a -> Maybe a
	fp [] _ = Nothing

evgenii-malov / bbst_dup.hs

Last active March 24, 2022 11:41

create balanced BST with duplicates in haskell

	-- GHCi, version 8.8.4
	-- explain video - https://www.youtube.com/watch?v=F6La0v_3hSM
	import Data.Maybe
	import PrettyT
	import Data.List
	-- data Btree a = Empty \| Node a (Btree a) (Btree a) deriving Show

	data Elem a = Single a \| Mult a Int deriving Show -- (a,Int)

	instance (Eq a) => Eq (Elem a) where

evgenii-malov / bsearch.hs

Last active March 24, 2022 11:41

binary search on a list and BST with Haskell

	-- GHCi, version 8.8.4
	-- explain video https://www.youtube.com/watch?v=LxbJS9L531g&t=798s
	import Data.Maybe
	import PrettyT
	-- data Btree a = Empty \| Node a (Btree a) (Btree a) deriving Show

	data LR = Lm \| Rm deriving Eq

	b :: Ord a => [a] -> a -> LR -> Maybe Int
	b [] _ _ = Nothing

evgenii-malov / balanced_from_sorted.hs

Last active February 23, 2022 20:13

create balanced tree from sorted list

	-- GHCi, version 8.8.4
	{-# LANGUAGE ScopedTypeVariables #-}
	import PrettyT -- https://www.youtube.com/watch?v=Ud-1Z0hBlB8&t=379s
	import Data.List
	import Data.Maybe
	-- data Btree a = Empty \| Node a (Btree a) (Btree a) deriving Show


	-- build balanced binary search tree from sorted list
	-- assume list is sorted

evgenii-malov / avl.hs

Last active February 2, 2022 14:47

AVL tree with Haskell

	-- GHCi, version 8.8.4
	-- author: Evgeniy Malov
	-- AVL delete: https://www.youtube.com/watch?v=DfSeb2fDH3s
	-- AVL insert: https://www.youtube.com/watch?v=SlAJirZ0KTE&t=0s
	{-# LANGUAGE ScopedTypeVariables #-}
	import Control.Monad
	import Data.Maybe
	import qualified Data.List as L
	import qualified Data.Map as M
	import PrettyT -- https://gist.github.com/evgenii-malov/1fc29a652751451dbca0d54d454cc1ef

Evgeniy Malov evgenii-malov